Consider the following statements about the context free grammar G = {S-->SS ,…

2016

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 ?

  1. A.

    I only

  2. B.

    I and III only

  3. C.

    II and III only

  4. D.

    I, II and III

Attempted by 21 students.

Show answer & explanation

Correct answer: B

Statement I is true because the production S->SS allows multiple parse trees for strings like "abab", making the grammar ambiguous.

Statement II is false because G cannot generate all strings with equal numbers of a's and b's, such as "aabb", since it only produces concatenations of "ab" and "ba".

Statement III is true because the language generated by G is regular, and thus can be accepted by a deterministic PDA. Therefore, the correct combination is I and III only.

Explore the full course: Isro