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.


2 Answers 2


$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
    Commented Jan 13, 2019 at 13:22
  • $\begingroup$ Correct! You are welcome. $\endgroup$
    – John L.
    Commented Jan 13, 2019 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 and acknowledge you have read our privacy policy.

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