The language of all non-null strings of a's can be defined by a context free…
2015
The language of all non-null strings of a's can be defined by a context free grammar as follow :
\(S \rightarrow a \: S \mid S\: a \mid a\)
The word 𝑎3 can be generated by ______ different trees.
- A.
Two
- B.
Three
- C.
Four
- D.
Five
Attempted by 138 students.
Show answer & explanation
Correct answer: C
Answer: Four parse trees.
Key idea: Each additional 'a' beyond the first can be attached either to the left or to the right of the substring generated so far. These choices are independent for each added 'a'.
Therefore, for a string of length n there are 2^(n-1) different parse trees. For n = 3 this gives 2^(2) = 4.
Attach left then attach left: S → a S → a a S → a a a (final S → a).
Attach left then attach right: S → a S → a S a → a a a.
Attach right then attach left: S → S a → a S a → a a a.
Attach right then attach right: S → S a → S a a → a a a (final S → a).
Thus the word a^3 can be generated by four different parse trees.