形式文法
1. S → a A {\displaystyle S\rightarrow aA}
2. A → a A {\displaystyle A\rightarrow aA}
3. A → b B {\displaystyle A\rightarrow bB}
4. B → b B {\displaystyle B\rightarrow bB}
5. B → b {\displaystyle B\rightarrow b}
6. S → ε {\displaystyle S\rightarrow \epsilon }
正規文法で生成される言語は、全て有限オートマトンで線形時間内で認識される。実際には正規文法は正規表現で表されるのが一般的だが、正規表現が必ずしも正規文法を表すためだけに使われるとは限らない。