A CFG G is given with the following productions where S is the start symbol, A…
2008
A CFG G is given with the following productions where S is the start symbol, A is a non-terminal and a and b are terminals.
S → aS∣A
A → aAb∣bAa∣ϵ
For the string "aabbaab" how many steps are required to derive the string and how many parse trees are there?
- A.
6 and 1
- B.
6 and 2
- C.
7 and 2
- D.
4 and 2
Attempted by 147 students.
Show answer & explanation
Correct answer: A
Derivation (leftmost): we show the sentential form after each production application.
S -> aS => aS
aS -> aA => aA
aA -> a aAb => aaAb
aaAb -> aa bAa b => aabAab
aabAab -> aab bAa ab => aabbAaab
aabbAaab -> aabb aab (apply A -> ε) => aabbaab
Total applications of productions: 6
Why the parse tree is unique:
S cannot go directly to A because A generates only even-length strings, while the target string has odd length; therefore S must produce an odd number of a's, forcing the first step S -> aS -> aA.
At each subsequent step the next production for A is forced by the next terminal in the target string (to get the required leftmost terminal), so there is no alternative choice that still matches the input.
Number of parse trees: 1
Answer: 6 steps and 1 parse tree.