Given Grammar $G$ with non-terminal symbols $N= \{S, A, B, C\}$ and terminal symbols $T=\{a,b\}$ and derives $P=\{ S \to B , B\to aBa, B\to bA, A\to bA , A\to C, C\to a \}$ and start symbol is S. Find the Language L(G) of grammar G and describe it as a set.
I think that $L(G) = \{abbaa, bba, ba\}$ . What do you think people?
But there is something that I REALLY cant understand.
Can we say this: $B\to aBa \to aaBaa \to aaaBaaa \to etc$ ?
this can continue to eternity, what can I do about it?
I mean every single of these words $(aBa , aaBaa , aaaBaaa .....)$ could lead us probably to words with terminals only $(abbaa, aabbaaa, aaabbaaaa )$ which looks like a pattern but different pattern compared to $\{abbaa, bba, ba\}$ .
I am so confused.
Thanks in advance!
$ S \to B \text{ (1)}\\ B\to aBa \text{ (2)}\\ B\to bA \text{ (3)}\\ A\to bA \text{ (4)}\\ A\to C \text{ (5)}\\ C\to a\text{ (6)}$
You should follow the way a string is made by applying rules of the grammar. In this grammar, starting with $S$ you should apply rule 1. Now you can apply rule 2 zero or more times, then you have to apply rule 3, then you can apply rule 4 zero or more times, then you have to apply rule 5 and after that rule 6.
So lets right this down:
Applying rule 1 we have:
$B$
Applying rule 2 zero or more times we have:
$a^nBa^n,n\geq0$
Applying rule 3 we have:
$a^nbAa^n,n\geq0$
After applying rule 4, $m$ times we will have($m\geq 0$):
$a^nbb^mAa^n,n,m\geq0$
Now we should apply rules 5 and 6, this gives us the final form of the strings of the language:
$a^nbb^maa^n,n,m\geq0$
Or equivalently:
$a^nb^{m+1}a^{n+1},n,m\geq0$
You should continue derivations until no nonterminal remains, only then the derivation is finished.
Note that derivations of strings is not always as straight forward as this grammar.