Рубрики

ВОРОТА | GATE 2017 MOCK II | Вопрос 41

Язык L = {WbcW R | W ∈ (a + b) *} есть _____.
(A) DCFL
(B) CFL, но не DCFL
(C) не-CFL
(D) Ничего из вышеперечисленного

Ответ: (А)
Объяснение: Любой язык, для которого у нас может быть детерминированный КПК, всегда является DCFL.
Здесь для языка L = {WbcWR | W ∈ (a + b) *} у нас может быть КПК со следующими переходами, в которых КПК принимает строку, когда он останавливается в конечном состоянии. q0 в начальном состоянии и qf — конечное состояние.

1. (q0, a, Z) -> (q0, aZ)

2. (q0, b, Z) -> (q0, bZ)

3. (q0, a, a) -> (q0, aa)

4. (q0, b, a) -> (q0, ba)

5. (q0, a, b) -> (q0, ab)

6. (q0, b, b) -> (q0, bb)

7. (q0, c, b) -> (q1, ноль)

8. (q1, a, a) -> (q1, ноль)

9. (q1, b, b) -> (q1, ноль)

10. (q1, ноль, Z) -> (qf, Z)

Здесь все a и b изначально помещаются в стек для W. Как только ac происходит после b, B извлекается из стека, после чего проверяется W ^ R. Если дальнейшие строковые алфавиты соответствуют
алфавит стека алфавит извлекается из стека и, наконец, строка достигает конечного состояния, если язык имеет вид L = {WbcW ^ R | W ∈ (a + b) *}.

Следовательно, вышеупомянутый язык является DCFL.

Тест на этот вопрос

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

ВОРОТА | GATE 2017 MOCK II | Вопрос 41

0.00 (0%) 0 votes