My book states that the language $$L_1 = \{a^nb^n\mid n\geq 1\}$$ is of type 2 (context-free) but not of type 3 (regular) since there is no regular grammar to produce it. However, I can't really imagine how this grammar should not be applicable or why it shouldn't be a valid type 3 grammar: $$S \to aS \mid bS \mid b\,.$$

For my understanding this grammar produces the language in question and also fulfils the type 3 criteria.


$S\Rightarrow bS\Rightarrow baS\Rightarrow bab$.

However, $bab$ is not $a^nb^n$ for any $n$.

(Exercise.) Is the following grammar a grammar for $L_1$?

$S \to Sa \mid Sb \mid a$

  • $\begingroup$ Exercise solution: No it's just the other way around and one can produce aba for instance. :) Thank you! $\endgroup$
    – OddDev
    Jan 13 '19 at 13:22
  • $\begingroup$ Correct! You are welcome. $\endgroup$
    – John L.
    Jan 13 '19 at 13:24

Your grammar produces every possible string that ends in $b$.

The proof that $\{a^nb^n\mid n\geq 1\}$ is not regular is standard and can be found in any textbook – use the pumping lemma, Myhill–Nerode or one of the other characterizations of regular languages.


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.