Рубрики

ВОРОТА | GATE CS 2011 | Вопрос 65

2) Рассмотрим язык L1, L2, L3, как указано ниже.
L1 = { | р, д N}
L2 = { | р, д N и p = q}
L3 = { | р, д, г N и p = q = r}

Какое из следующих утверждений не верно ?
(A) Автоматы Push Down (PDA) могут использоваться для распознавания L1 и L2
(B) L1 — обычный язык
(C) Все три языка не зависят от контекста
(D) Машина Тьюринга может использоваться для распознавания всех трех языков

Ответ: (с)
Пояснение: L1 регулярно. Его DFA дается как

       

L2 не является регулярным, это можно доказать с помощью леммы о накачке (см. Ульман). Но L2 это КЛЛ.

        S → AB
        A → 0A|ε
        B → 1B|ε

L3 не является КЛЛ, может быть доказано с помощью леммы прокачки (см. Ульман). Но L3 является рекурсивным.

Каждый обычный язык также является КЛЛ. Таким образом, КПК можно использовать для распознавания L1 и L2.
Как CFL и Regular язык также является рекурсивным языком. Следовательно, машина Тьюринга может быть использована для распознавания
L1, L2 и L3.
L2 не является регулярным, это можно доказать с помощью леммы о накачке (см. Ульман). Но L2 это КЛЛ.

        S → AB
        A → 0A|ε
        B → 1B|ε

L3 не является КЛЛ, может быть доказано с помощью леммы прокачки (см. Ульман). Но L3 является рекурсивным.

Каждый обычный язык также является КЛЛ. Таким образом, КПК можно использовать для распознавания L1 и L2.
Как CFL и Regular язык также является рекурсивным языком. Следовательно, машина Тьюринга может быть использована для распознавания
L1, L2 и L3.

Источник: http://clweb.csa.iisc.ernet.in/rahulsharma/gate2011key.html
Тест на этот вопрос

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

ВОРОТА | GATE CS 2011 | Вопрос 65

0.00 (0%) 0 votes