Consider the CFG with {S,A,B) as the non-terminal alphabet, {a,b) as the…

2007

Consider the CFG with {S,A,B) as the non-terminal alphabet, {a,b) as the terminal alphabet, S as the start symbol and the following set of production rules 

S --> aB        S --> bA
B --> b         A --> a
B --> bS        A --> aS
B --> aBB       A --> bAA

Which of the following strings is generated by the grammar?

  1. A.

    aaaabb

  2. B.

    aabbbb

  3. C.

    aabbab

  4. D.

    abbbba

Attempted by 14 students.

Show answer & explanation

Correct answer: C

To determine which string is generated by the given CFG, we analyze the production rules. Starting from S, we can derive strings using S → aB or S → bA. The rules for A and B allow expansion to terminal symbols (a, b) or recursive calls with S. Option D: 'abbbba' can be derived as follows: S → bA → baS → babA → babbB → abbbba (after applying B → b and other rules). This sequence is valid. Option A: 'aaaabb' fails because it requires more a's than b's in an unbalanced way, violating the grammar’s structure.

Explore the full course: Gate Guidance By Sanchit Sir