Рубрики

ВОРОТА | Gate IT 2005 | Вопрос 38

Пусть P будет недетерминированным автоматом нажатия (NPDA) с ровно одним состоянием q и ровно одним символом Z в его стековом алфавите. Состояние q является как начальным, так и принимающим состоянием КПК. Стек инициализируется одним Z перед началом работы КПК. Пусть входным алфавитом КПК будет Σ. Пусть L (P) будет языком, принятым КПК, читая строку и достигая ее состояния принятия. Пусть N (P) будет языком, принятым КПК, читая строку и освобождая ее стек.
Какие из следующих утверждений верно?

(A) L (P) обязательно Σ *, но N (P) не обязательно Σ *
(B) N (P) обязательно Σ *, но L (P) не обязательно Σ *
(C) L (P) и N (P) обязательно являются Σ *
(D) Ни L (P), ни N (P) не обязательно являются Σ *

Ответ: (D)
Пояснение: Язык L (P), принятый автоматами Push Down (PDA), при чтении строки и достижении
его принимающее состояние и язык N (P), принятый КПК путем чтения
строка и очистка стека, но это может быть случай, когда строка имеет
мертвая конфигурация на переходах кпк т.е. кпк не имеет
переход для определенного алфавита или строки. Следовательно, он не принимает
все строки над Σ *.

For example- Transitions for the PDA are as follows:
1. (q, a, Z) -> (q, aZ)
2. (q, b, Z) -> (q, bZ)
3. (q, a, a) -> (q, aa)
4. (q, a, b) -> (q, ab)
5. (q, b, a) -> (q, ba)
6. (q, null, Z) -> (q, Z)
7. (q, null ,a) -> (q, null)
8. (q, null, b) -> (q, null)

Здесь q — начальное и принимающее состояние, Z — начальный символ стека.
и a и b — входные алфавиты. Здесь {null, a, b, ab, aab ……… ..}
принимаются в обоих случаях, но в случае «bb» КПК попадает в мертвый
Конфигурация как такового такого перехода отсутствует. Следовательно, ни L (P), ни N (P)
быть обязательно Σ *.

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

ВОРОТА | Gate IT 2005 | Вопрос 38

0.00 (0%) 0 votes