Рубрики

ВОРОТА | GATE IT 2006 | Вопрос 31

Какой из следующих языков принимается недетерминированным автоматом нажатия (PDA), но НЕ детерминированным PDA?
(A) {a n b n c n ∣ n≥0}
(B) {a l b m c n ∣ l ≠ m или m ≠ n}
(C) {a n b n ∣ n≥0}
(D) {a m b n ∣ m, n≥0}

Ответ: (Б)
Объяснение:

1. L = {anbncn | n> = 0} это не CFL, так как нет КПК, который мог бы получить этот язык.
То же самое можно доказать с помощью леммы прокачки, что также можно увидеть на интуитивном уровне. [НЕПРАВИЛЬНЫЙ]

2. L = {albmcn | l! = м или м! = n} является объединением двух КЛЛ L1 = {albmcn | l! = m} и L2 =
{albmcn | m! = n} оба имеют DPDA. Следовательно, L уверен, что КЛЛ, таким образом, он будет иметь DFA,
хотя не обязательно детерминированный. L = {anbncn} и DPDA закрыты под
комплементация — таким образом, если L является DPDA, то его дополнение должно быть также DPDA,
что не соответствует действительности. Следовательно, L принимается NPDA. [ВЕРНЫЙ]

3. L = {anbn | n ≥ 0} может быть получен из детерминированного КПК — нажмите, если текущий алфавит
и поп, если это б. Принять, если стек в конце строки пуст, и отклонить в противном случае. [НЕПРАВИЛЬНЫЙ]

4. L = {anbm | n, m ≥ 0} — регулярный язык вида a ∗ b ∗, следовательно, он имеет DPDA. [НЕПРАВИЛЬНЫЙ]

Ссылка :

https://cs.wmich.edu/elise/courses/cs6800/DCFL.pptx

Это решение предоставлено Винет Пурсвани .
Тест на этот вопрос

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

ВОРОТА | GATE IT 2006 | Вопрос 31

0.00 (0%) 0 votes