文脈自由文法
文字セット {a,b} について、異なる個数の a と b から構成される全ての文字列を生成する文脈自由文法は以下のようになる。
S → U | V U → TaU | TaT V → TbV | TbT T → aTbT | bTaT | ε
ここで、T に関する生成規則は a と b が同数の文字列を生成するが、U は a の方が必ず多くなる文字列を生成し、V は b の方が必ず多くなる文字列を生成する。