Gate Bits 3 CFL and PDA
In this class, we discuss Gate Bits 3 CFL and PDA.
For Complete YouTube Video: Click Here
The reader should have prior knowledge of CFL and PDA. Click Here.
Gate 2003
Let G = ({S}, {a, b} R, S) be a context free grammar where the rule set R is
S → a S b | SS | ε
Which of the following statements is true?
(A) G is not ambiguous
(B) There exist x, y, ∈ L (G) such that xy ∉ L(G)
(C) There is a deterministic push-down automaton that accepts L(G)
(D) We can find a deterministic finite state automaton that accepts L(G)
Answer: c
The language generated by the grammar (aⁿbⁿ)*
Deterministic Push down automata possible for the language.
Explanation provided in the above video.
Gate 2005:
Let Nf and Np denote the classes of languages accepted by non-deterministic finite automata and non-deterministic push-down automata, respectively.
Let Df and Dp denote the classes of languages accepted by deterministic finite automata and deterministic push-down automata, respectively.
Which one of the following is TRUE?
(A) Df ⊂ Nf and Dp ⊂ Np
(B) Df ⊂ Nf and Dp = Np
(C) Df = Nf and Dp = Np
(D) Df = Nf and Dp ⊂ Np
Answer: D
There is no standard procedure to convert NDPDA to DPDA. It is not possible to convert.