チョムスキー階層
B A → A B {\displaystyle BA\rightarrow AB}
B S → b {\displaystyle BS\rightarrow b}
B b → b b {\displaystyle Bb\rightarrow bb}
A b → a b {\displaystyle Ab\rightarrow ab}
A a → a a {\displaystyle Aa\rightarrow aa}
これにより開始記号 S {\displaystyle S} から定義される全単語で構成される言語は a n b n {\displaystyle a^{n}b^{n}\quad } である( n {\displaystyle n} 個の a {\displaystyle a} の後に n {\displaystyle n} 個の b {\displaystyle b} が続く形式)。同様の言語をもっと単純な文法で定義した例を以下に示す。終端記号 { p , q } {\displaystyle \{p,q\}} 、非終端記号 { S } {\displaystyle \{S\}} 、開始記号 S {\displaystyle S} で生成規則は以下のようになる。
S → p S q {\displaystyle S\rightarrow pSq} S → ε {\displaystyle S\rightarrow \epsilon }