# Does this grammar accept this words?

I made this grammar:

$$S \rightarrow ASa$$

$$S \rightarrow c$$

$$A \rightarrow a|b$$

And I want to check that it accepts words like $$aacaa$$, $$abcaa$$, $$babcaaa$$, I formed the grammar by thinking about the typical $$a ^ nb ^ n$$,but I added what is necessary for my interest.

## 1 Answer

It looks like the grammar indeed accepts all words of the form $$[b+a]^nca^n$$ (which means, all words that start with any sequence of $$n$$ $$b$$'s and $$a$$'s, and then a single $$c$$ and afterward exactly $$n$$ times the letter $$a$$).

To show why to try to show the two following things:

1. every word accepted by the grammar must be in such form

2. every word with such form has a derivation sequence in the grammar.

The first statement can be easily proved by induction (over sequence derivation length) if you notice that each derivation of $$S$$ adds only one element to both sides.

The second statement can be much more easily proved, try to think of what derivations are necessary to create such words.