形式文法
S ⟶ ( 1 ) a B S c ⟶ ( 2 ) a B a b c c ⟶ ( 3 ) a a B b c c ⟶ ( 4 ) a a b b c c {\displaystyle {\boldsymbol {S}}\longrightarrow (1)aB{\boldsymbol {S}}c\longrightarrow (2)a{\boldsymbol {Ba}}bcc\longrightarrow (3)aa{\boldsymbol {Bb}}cc\longrightarrow (4)aabbcc}
S ⟶ ( 1 ) a B S c ⟶ ( 1 ) a B a B S c c ⟶ ( 2 ) a B a B a b c c c ⟶ ( 3 ) a a B B a b c c c ⟶ ( 3 ) a a B a B b c c c {\displaystyle {\boldsymbol {S}}\longrightarrow (1)aB{\boldsymbol {S}}c\longrightarrow (1)aBaB{\boldsymbol {S}}cc\longrightarrow (2)a{\boldsymbol {Ba}}Babccc\longrightarrow (3)aaB{\boldsymbol {Ba}}bccc\longrightarrow (3)aa{\boldsymbol {Ba}}Bbccc} ⟶ ( 3 ) a a a B B b c c c ⟶ ( 4 ) a a a B b b c c c ⟶ ( 4 ) a a a b b b c c c {\displaystyle \longrightarrow (3)aaaB{\boldsymbol {Bb}}ccc\longrightarrow (4)aaa{\boldsymbol {Bb}}bccc\longrightarrow (4)aaabbbccc}
1. S → a S b {\displaystyle S\rightarrow aSb}
2. S → a b {\displaystyle S\rightarrow ab}
文脈自由言語はアーリー法のようなアルゴリズムを使って O ( n 3 ) {\displaystyle O(n^{3})} の時間(ランダウの記号参照)で認識可能である。すなわち、全ての文脈自由言語について、任意の文字列を入力とし、それが特定の言語に含まれるかどうかを O ( n 3 ) {\displaystyle O(n^{3})} の時間内に決定する機械を構築できる。ここで、 n {\displaystyle n} は入力文字列長である。さらに、文脈自由言語の重要なサブセットは他のアルゴリズムを使って線形時間で認識可能である。