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