Gate Bits 4 CFL and PDA

In this class, we discuss Gate Bits 4 CFL and PDA.

For Complete YouTube Video: Click Here

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

Gate 2006:

Consider the following statements about the context free grammar.

G={S→SS,S→ab,S→ba,S→ϵ}

I: G is ambiguous

II: G produces all strings with equal number of a’s and b’s

III: G can be accepted by a deterministic PDA.

Which combination below expresses all the true statements about G?

(A) I only

(B) I and III only

(C) II and III only

(D) I, II and III

Answer: B

Explanation given in the above video.

Gate 2008:

Which of the following statements are true?

I: Every left-recursive grammar can be converted to a right-recursive grammar and vice-versa

II: All ϵ-productions can be removed from any context-free grammar by suitable transformations

III: The language generated by a context-free grammar all of whose productions are of the form X→w or X→wY

(where, w is a string of terminals and Y is a non-terminal), is always regular

IV: The derivation trees of strings generated by a context-free grammar in Chomsky Normal Form are always binary trees

(A) I, II, III and IV

(B) II, III and IV only

(C) I, III and IV only

(D) I, II and IV only

Answer: C

Explanation provided in the above video