Consider the CFG with {S, A, B} as the non-terminal alphabet, {a, b} as the…
2021
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 → bA S → aB
A → a B → b
A → aS B → bS
S → bAA B → aBB
Which of the following strings is generated by the grammar?
Answer: C. aabbab — Try derivation using rules: S → aB B → bS S → aB B → b A → a One valid derivation: S ⇒ aB ⇒ abS ⇒ abaB ⇒ abab ⇒ aabbab (using recursive expansions with A → a,…
- A.
aaaabb
- B.
aabbbb
- C.
aabbab
- D.
Abbba
- E.
Question not attempted
Attempted by 39 students.
Show answer & explanation
Correct answer: C
Try derivation using rules:
S → aB
B → bS
S → aB
B → b
A → a
One valid derivation:
S ⇒ aB
⇒ abS
⇒ abaB
⇒ abab
⇒ aabbab (using recursive expansions with A → a, B → bS / b)
Hence, aabbab can be generated.