Chomsky 1

I’m learning automata and formal languages for my final exams. As a test I constructed a grammar for

a ^{n^ b ^n} c ⁿ with n >= 1

which seems to be correct and somewhat better than the ones found in literature:

S -> aSBc

S -> aBc

cB -> Bc

aB -> ab

bB -> bb

However, it strikes me as odd that I may have found a shorter and slightly better grammar than:

S -> aSBC

S -> aBC

CB -> BC

aB -> ab

bB -> bb

bC -> bc

cC -> cc

In the latter you can run into situations that end up with something like aabcBC and end up with a word that you can’t go on with. With my grammar you always end up with a real word.

However, I don’t think I can be the first one to have found that grammar. So if you know that it isn’t correct, or that someone has published it somewhere, please correct me ;-)

P.S.: the wikipedia had a similiar grammar on it’s page, but it was simply wrong. I corrected it to my grammar which I think is correct. Maybe that will verify it quickly ;-)

Update: the wikipedia’s grammar was right. I corrected it back. Bad me. While mine wasn’t wrong, the wikipedia’s is even shorter:

S -> aSBc

S -> abc

cB -> Bc

bB -> bb

it just folded the S -> aBc -> abc rule into one.