文脈依存文法
文脈依存文法で記述できる言語として { a n b n c n d n : n ≥ 1 } {\displaystyle \{a^{n}b^{n}c^{n}d^{n}:n\geq 1\}} というものもあるが、これの生成規則は上記のものより更に複雑になる。
この文法で「aaabbbccc」をマッチさせるときの流れは、以下のようになる。
S
→ aSBC
→ aaSBCBC
→ aaaBCBCBC
→ aaaBHBCBC
→ aaaBHCCBC
→ aaaBBCCBC
→ aaaBBCHBC
→ aaaBBCHCC
→ aaaBBCBCC
→ aaaBBHBCC
→ aaaBBHCCC
→ aaaBBBCCC
→ aaabBBCCC
→ aaabbBCCC
→ aaabbbCCC
→ aaabbbcCC
→ aaabbbccC
→ aaabbbccc
上の例を弱等価な単調文法で書くと、以下のようになる。
S → abc | aSBc
cB → Bc
bB → bb
文脈依存文法の例を以下に示す。
S → aSBC | aBC
CB → HB
HB → HC
HC → BC
aB → ab
bB → bb
bC → bc
cC → cc
ここで、| は同じ非終端記号からの生成規則を列挙する代わりに一行で表記するために用いられている。この文法が生成する言語は { a n b n c n : n ≥ 1 } {\displaystyle \{a^{n}b^{n}c^{n}:n\geq 1\}} であり、これは文脈自由言語ではない。文脈依存文法では生成規則を適用する際に複数の文字(文字列)に対してパターンマッチさせるようになっており、マッチすべき文字数に制限はない。一方で文脈自由文法ではパターンマッチするのは常に一文字(非終端記号)である。