
▶
## 2.
Let \( G \) be the context-free grammar with non-terminal symbols
\( V = \{S, A, B\} \), terminal symbols \( \Sigma = \{a, b\} \), start symbol \( S \),
and productions \( P \):
- \( S \to ABb \)
- \( S \to Bb \)
- \( A \to aB \)
- \( A \to b \)
- \( B \to ab \)
- \( B \to \epsilon \)
### Which of these strings can be generated by \( G \)?
(a) ab
(b) bb
(c) baaba
(d) aababb
(e) abb
(f) bbb
---
### Solution
All strings must end in **b**, that eliminates **(c)**.
It isn’t possible to make three consecutive **b**’s, so **(f)** is eliminated.
**(a), (b), (d), and (e)** are all generated by \( G \).

▶
Let G be the context-free grammar with non-terminal symbols V = {S, A, B}, terminal
symbols Σ = {a, b}, start symbol S, and productions P:
• S → ABb
• S → Bb
• A → aB
• A → b
• B → ab
• B → ϵ
Which of these strings can be generated by G?
(a) ab
(b) bb
(c) baaba
(d) aababb
(e) abb
(f) bbb