Gate Bits 1 CFL and PDA

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

For Complete YouTube Video: Click Here

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

Gate 2009:

S -> aSa|bSb|a|b; The language generated by the above grammar over the alphabet {a,b} is the set of

1) All palindromes

2) All odd length palindromes.

3) Strings that begin and end with the same symbol

4) All even length palindromes

Answer: 2

Gate 2016:

Language L1 is defined by the grammar: S1→aS1b∣ε

Language L2 is defined by the grammar: S2→abS2∣ε

Consider the following statements:

P: L1 is regular

Q: L2 is regular

Which one of the following is TRUE?

1) Both P and Q are true.

2) P is true and Q is false.

3) P is false and Q is true.

4) Both P and Q are false.

Answer: 3

Gate 2006

Let

{L1={0^(n+m)1^n0^m |n,m≥0}

L2={0^(n+m)1^(n+m)0^m ∣n,m≥0}

L3={0^(n+m)1^(n+m)0^(n+m) ∣n,m≥0}

Which of these languages are NOT context free?

1) L1only

2) L3 only

3) L1 and L2

4) L2 and L3

Answer: 4

Explanation is provided in the video.