# Why is $\{a^nb^n \mid n \geq 1\}$ not type 3 (regular)?

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

$$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$$

• Exercise solution: No it's just the other way around and one can produce aba for instance. :) Thank you! – OddDev Jan 13 at 13:22
• Correct! You are welcome. – Apass.Jack Jan 13 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.