2004-gre-cs-practice-book.pdf/Q59 — различия между версиями

Текущая версия на 09:00, 16 декабря 2024

Вопрос: Q59-4c9f66

Рассмотрите следующие два языка

Что из нижеследующего верно в отношении и  ?

Ответы

• и являются регулярными
• регулярный, а контекстно-свободный, но не регулярный
• Ни , ни не являются регулярными, но оба они не зависят от контекста.
• Правильный ответ: является контекстно-свободным, но не регулярным, и не является контекстно-свободным.
• Ни , ни не являются контекстно-свободными.

Объяснение

Исходники — вопрос 59 на 39 странице книги «2004-gre-cs-practice-book.pdf»

• Фишки типа равенства количества символов нельзя положить на конечный автомат, так что оба нерегулярны.
• Но L1 можно положить на автомат с магазином, если держать на стеке разницу двух типов символов.
• А L2 даже магазинным автоматом не взять, так что он также и не КС.