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.


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.