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.