2011-gre-cs-practice-book.pdf/Q05 — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
| (не показаны 3 промежуточные версии этого же участника) | |||
| Строка 1: | Строка 1: | ||
| − | |||
== Вопрос: Q05-08c765 == | == Вопрос: Q05-08c765 == | ||
| − | |||
| − | |||
| − | |||
<graph> | <graph> | ||
digraph G{ | digraph G{ | ||
| Строка 13: | Строка 9: | ||
T -> U [label="y"] | T -> U [label="y"] | ||
U -> U [label="y"] | U -> U [label="y"] | ||
| − | U -> V [label="x" shape= | + | U -> V [label="x"] |
| + | V [shape=doublecircle] | ||
} | } | ||
</graph> | </graph> | ||
| Строка 20: | Строка 17: | ||
Какая из следующих грамматик над алфавитом x, y генерирует язык, распознаваемый автоматом выше? | Какая из следующих грамматик над алфавитом x, y генерирует язык, распознаваемый автоматом выше? | ||
| − | === | + | === Ответ === |
| − | + | S → xT | |
| − | + | T → xT | xU | yU | |
| − | + | U → yU | xV | |
| − | + | ||
| − | + | ||
| + | === Правильный ответ === | ||
| + | S → xT | ||
| + | T → xT | xU | yU | ||
| + | U → yU | x | ||
| + | |||
| + | === Ответ === | ||
| + | S → xT | T | ||
| + | T → xT | xU | yU | T | U | ||
| + | U → yU | xV | V | x | ||
| + | |||
| + | === Ответ === | ||
| + | S → xV | ||
| + | T → xT | yU | ||
| + | U → yU | xV | ||
| + | |||
| + | === Ответ === | ||
| + | S → xT | ||
| + | T → xT | T | ||
| + | U → yU | V | ||
| + | V → xV | x | ||
=== Объяснение === | === Объяснение === | ||
| Строка 33: | Строка 48: | ||
Очевидно: | Очевидно: | ||
| − | + | ||
| − | + | Варианты [[File:CC.png]] и [[File:ddd.png]] сразу отметаем, есть только <m>S→xT</m> | |
| − | + | ||
| − | + | Вариант [[File:AA.png]] не подходит, т.к нет <m>U→xV</m> | |
| − | {{question-ok | + | |
| − | + | Вариант [[File:EE.png]] не подходит, т.к из терминального состояния <m>V</m> мы никуда не идём | |
| + | |||
| + | Вариант [[File:BB.png]] подходит идеально | ||
| + | |||
| + | {{question-ok|[[Участник:StasFomin|StasFomin]] 15:06, 19 декабря 2024 (UTC)}} | ||
| + | |||
| + | [[Категория:Формальные языки]] | ||
Текущая версия на 15:08, 19 декабря 2024
Содержание
Вопрос: Q05-08c765
Какая из следующих грамматик над алфавитом x, y генерирует язык, распознаваемый автоматом выше?
Ответ
S → xT T → xT | xU | yU U → yU | xV
Правильный ответ
S → xT T → xT | xU | yU U → yU | x
Ответ
S → xT | T T → xT | xU | yU | T | U U → yU | xV | V | x
Ответ
S → xV T → xT | yU U → yU | xV
Ответ
S → xT T → xT | T U → yU | V V → xV | x
Объяснение
Исходники — вопрос 5 на 16 странице книги «2011-gre-cs-practice-book.pdf»
Очевидно:
Варианты 
и 
сразу отметаем, есть только
Вариант 
не подходит, т.к нет
Вариант 
не подходит, т.к из терминального состояния мы никуда не идём
Вариант 
подходит идеально