Consider the context-free grammar G below S → aSb | X X → aX | Xb | a | b ,…
2023
Consider the context-free grammar G below
S → aSb | X
X → aX | Xb | a | b ,
where S and X are non-terminals, and a and b are terminal symbols. The starting non-terminal is S.
Which one of the following statements is CORRECT?
- A.
The language generated by G is (a + b)∗
- B.
The language generated by G is a∗(a + b)b∗
- C.
The language generated by G is a∗b∗(a + b)
- D.
The language generated by G is not a regular language
Attempted by 81 students.
Show answer & explanation
Correct answer: B
Key insight: every string generated has all a's before all b's and is non-empty.
Step 1: Describe strings from X. X → aX | Xb | a | b produces either a or b as a base, with any number of additional a's added on the left and any number of b's added on the right. So L(X) = a+ b* ∪ a* b+ = a*(a+b)b*, i.e. all non-empty strings of the form a* b*.
Step 2: Describe strings from S. S → aSb | X gives L(S) = { a^n x b^n | n ≥ 0, x ∈ L(X) } = { a^{n+p} b^{n+q} | p+q ≥ 1 }.
Conclusion: The set { a^{r} b^{s} | r,s ≥ 0 and not both zero } equals a* b* without the empty string, which can be written as a*(a+b)b*. Therefore the language of G is a*(a+b)b*, and it is a regular language.