I'm trying to solve an exercise on grammars and languages. Here is the exercise:
Let the grammar G be:
G = {V, T, P, S},
V = {S, A, B},
T = {a, b, c},
P = {S → ABA; A → a | bb; B → bS | ε}
What language is generated by this grammar?
I've tried to derive every possible words accepted by this grammar, but I just can't seem to find a pattern. Anyone can help me with this problem?
Here is the original grammar:
S → ABA
A → a | bb
B → bS | ε
We can substitute for A and B so S is all that's left:
S → (a + bb)(bS + ε)(a + bb)
Distributing and rearranging a bit:
S → (a + bb)bS(a + bb) + (a + bb)(a + bb)
It can be shown that
X → rXs + t
iff
X → (r^n)t(s^n)
In our case:
S → (ab + bbb)^n (a + bb)^2 (a + bb)^n
I am not sure there is a super satisfying English language description of these strings, but maybe it gives a more inuitive representation than the grammar does? To each his own.