Рубрики

ВОРОТА | GATE-CS-2005 | Вопрос 57

GATE

Рассмотрим языки:

L1 = {wwR |w ∈ {0, 1}*}
L2 = {w#wR | w ∈ {0, 1}*}, where # is a special symbol
L3 = {ww |  w ∈  (0, 1}*)

Что из следующего является ИСТИННЫМ?
(A) L1 является детерминированным КЛЛ
(B) L2 является детерминированным КЛЛ
(C) L3 является КЛЛ, но не детерминированным КЛЛ
(D) L3 является детерминированным КЛЛ

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

L1: {ww ^ R | w принадлежит {0,1} *}
Это CFL, но не DCFL. Это может быть получено из следующей грамматики
S -> aSa | bSb | эпсилон
Но он не может быть получен из какого-либо детерминированного автомата нажатия, потому что нет способа выяснить, где заканчивается слово w и начинается его обратное.

L2: {w # w ^ R | w принадлежит {0,1} *}
Это КЛЛ по той же причине, что и описанная выше. Это детерминированный КЛЛ, потому что у нас есть маркер, который поможет нам узнать конец слова w и начало его обратного. Таким образом, КПК, где все алфавиты будут сдвинуты до тех пор, пока мы не получим #, а затем выскочит только в том случае, если вершина стека соответствует текущему алфавиту и отвергнет в противном случае — получит L2.

L3: {ww | w принадлежит {0,1} *}
Это даже не КЛЛ. Вышеприведенное утверждение может быть доказано с использованием леммы прокачки —
Рассмотрим строку z вида (0 ^ n 1 ^ n 0 ^ n 1 ^ n).
Предполагая, что L3 является КЛЛ, и z, очевидно, удовлетворяет L3 — таким образом, z также должен удовлетворять лемме о накачке.
Мы возьмем n так, что n = p, где p — длина накачки L3, поэтому длина нашей струны должна быть больше длины накачки.
Теперь, согласно лемме прокачки, должны существовать такие u, v, w, x, y, что z = uvwxy, | vwx | <= p, | vx | > 0 и u {v ^ i} x {y ^ i} z принадлежит L3 для всех i> = 0.
Не существует такой конфигурации u, v, w, x, y, что u {v ^ 0} x {y ^ 0} z принадлежит L3. Следовательно, z не удовлетворяет лемме накачки. Следовательно, L3 не является КЛЛ.

Учитывая все вышеперечисленные выводы, единственным правильным вариантом является (B) L2 — детерминированный КЛЛ.

Ссылка ;

https://courses.engr.illinois.edu/cs373/sp2013/Lectures/lec17.pdf

Это решение предоставлено Vineet Purswani .
Тест на этот вопрос

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

ВОРОТА | GATE-CS-2005 | Вопрос 57

0.00 (0%) 0 votes