2011-gre-cs-practice-book.pdf/Q05 — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Новая страница: « == Вопрос: Q05-08c765 == <i>Тут вставьте перевод вопроса. Используйте [https://wiki.4intra.net/Help:%D0%A4%D0%BE%D1%80…») |
StasFomin (обсуждение | вклад) |
||
(не показано 49 промежуточных версий 2 участников) | |||
Строка 1: | Строка 1: | ||
− | |||
== Вопрос: Q05-08c765 == | == Вопрос: Q05-08c765 == | ||
+ | <graph> | ||
+ | digraph G{ | ||
+ | rankdir=LR; | ||
+ | edge [color=blue]; | ||
+ | S -> T [label="x"] | ||
+ | T -> T [label="x"] | ||
+ | T -> U [label="x"] | ||
+ | T -> U [label="y"] | ||
+ | U -> U [label="y"] | ||
+ | U -> V [label="x"] | ||
+ | V [shape=doublecircle] | ||
+ | } | ||
+ | </graph> | ||
− | |||
− | |||
− | |||
− | |||
− | + | Какая из следующих грамматик над алфавитом 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 | ||
=== Объяснение === | === Объяснение === | ||
− | |||
− | |||
− | + | {{cstest-source|2011-gre-cs-practice-book.pdf|16|5}} | |
+ | |||
+ | Очевидно: | ||
+ | |||
+ | Варианты [[File:CC.png]] и [[File:ddd.png]] сразу отметаем, есть только <m>S→xT</m> | ||
+ | |||
+ | Вариант [[File:AA.png]] не подходит, т.к нет <m>U→xV</m> | ||
+ | |||
+ | Вариант [[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»
Очевидно:
Варианты и сразу отметаем, есть только
Вариант не подходит, т.к из терминального состояния мы никуда не идём