Multiple choice

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 $\rightarrow$ aB S $\rightarrow$ bA B $\rightarrow$ b A $\rightarrow$ a B $\rightarrow$ bS A $\rightarrow$ aS B $\rightarrow$ aBB S $\rightarrow$ bAA

How many derivation trees are there?

  1. 1

  2. 2

  3. 3

  4. 4
Reveal answer Fill a bubble to check yourself
B Correct answer
Explanation

S $\rightarrow$ aB $\rightarrow$ aBB $\rightarrow$ abSbS $\rightarrow$ abbAbaB $\rightarrow$ abbabab S $\rightarrow$ bA $\rightarrow$ baS $\rightarrow$ babAA $\rightarrow$ babaSaS $\rightarrow$ bababAabA $\rightarrow$ bababaaba

Keep practicing — related questions