Рубрики

ВОРОТА | GATE-CS-2016 (набор 2) | Вопрос 27

Language L1 is defined by the grammar: S1 -> aS1b | ε
Language L2 is defined by the grammar: S2 -> abS2 | ε

Рассмотрим следующие утверждения:

P: L1 is regular
Q: L2 is regular

Что из следующего является ИСТИННЫМ?
(A) P и Q верны
(B) P истинно, а Q ложно
(C) P ложно и Q верно
(D) P и Q ложны

Ответ: (с)
Объяснение: L1 обладает тем свойством, что ни одно из a не должно быть равно ни одному из b в строке, и все a должны предшествовать всем b. Следовательно, для проверки этого свойства строки потребуется дополнительная память (конечный автомат не может быть построен для этого типа языка). Следовательно, это не обычный язык. Следовательно, P ложно.

L2 обладает тем свойством, что ни одно из a не должно быть равным ни одному из b, но здесь порядок a и b отличается, это (ab) *, что не требует принятия дополнительной памяти. (Конечный автомат может быть построен для этот язык). Следовательно, L2 регулярный язык. Следовательно, Q — это Истина.
Тест на этот вопрос

Рекомендуемые посты:

ВОРОТА | GATE-CS-2016 (набор 2) | Вопрос 27

0.00 (0%) 0 votes