Gate Bits 2 CFL and PDA

In this class, We discuss Gate Bits 2 CFL and PDA.

For Complete YouTube Video: Click Here

The reader should have prior knowledge of the concepts CFL and PDA. Click Here.

Gate 2017:

Identify the language generated by the following grammar, where S is the start variable.

SXY

XaXa

YaYbϵ

1) {a^mb^nmn,n>0}

2) {a^mb^nmn,n≥0}

3) {a^mb^nm>n,n≥0}

4) {a^mb^nm>n,n>0}

Answer: 3

Gate 97:

Which of the following languages over {a,b,c} is accepted by a deterministic pushdown automata?

a. {wcwR ∣ w∈ {a,b}* }

b. {wwR ∣ w∈ {a,b,c}* }

c. {anbncn ∣ n ≥ 0 }

d. {w ∣ w is a palindrome over {a,b,c} }

Note: wR  is the string obtained by reversing ‘w

1) a

2) b

3) c

4) d

Answer: 1

Explanation Provided in the video.