btccc

『壹』 上下文有关文法的例子

以下文法生成正规的非上下文无关语言
S → aRc
R → aRT | b
bTc → bbcc
bTT → bbUT
UT → UU
UUc → VUc → Vcc
UV → VV
bVc → bbcc
bVV → bbWV
WV → WW
WWc → TWc → Tcc
WT → TT
可以使用更复杂的文法解析 和其他有更多字母的语言。
aaa bbb ccc 的产生链是：
S
aRc
aaRTc
aaaRTTc
aaabTTc
aaabbUTc
aaabbUUc
aaabbVUc
aaabbVcc
aaabbbccc
aaaa bbbb cccc 的产生链是：
S
aRc
aaRTc
aaaRTTc
aaaaRTTTc
aaaabTTTc
aaaabbUTTc
aaaabbUUTc
aaaabbUUUc
aaaabbUVUc
aaaabbUVcc
aaaabbVVcc
aaaabbbWVcc
aaaabbbWWcc
aaaabbbTWcc
aaaabbbTccc
aaaabbbbcccc