Рубрики

ВОРОТА | GATE-CS-2003 | Вопрос 90

Пусть G = ({S}, {a, b} R, S) — грамматика без контекста, где набор правил R
S → a S b | СС | ε
Какие из следующих утверждений верно?
(А) G не является двусмысленным
(B) Существуют x, y, ∈ L (G) такие, что xy ∉ L (G)
(C) Существует детерминированный автомат, который принимает L (G)
(D) Мы можем найти детерминированный конечный автомат, который принимает L (G)

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

An ambiguous grammar can be converted to unambiguous one.

Here we can get grammar in partial GNF form as
S -> ab | abS | aSb | aSbS

We can convert this into GNF too but no need for PDA reasoning
so, above grammar is not a ambiguous thus a definite PDA possible

Trick for this is but just deriving 3-4 strings from grammar, we 
can easily understand its (anbn)* above 
expression anbn is in CFL thus closure of DCFG is a DCFG
i.e., you can get L = {ε, ab, abab, aabb, aabbab, abaabb, 
ababab,......}
PDA will push "a" until "b" is read, start popping "a" for the "b" read.

If "a" is read again from the tape then push only when stack is empty 
else terminate.

Repeat this until string is read.

Remember fastest way to get answer is by elimination other options.

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

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

ВОРОТА | GATE-CS-2003 | Вопрос 90

0.00 (0%) 0 votes