context-free-grammar - CFL 泵送引理 L = {a^nb^mc^kd^k | n>m}

Question

我在使用上下文无关的抽引引理解决这个练习时遇到了一些麻烦。有人可以帮忙吗？

Answer 1

使用正则语言的抽引引理可以证明这种语言不是正则的。它是上下文无关的，这是它的语法：

S -> LR
L -> a | aL | aLb
R -> e | cRd 

基本上，认识到 a/b 部分与 c/d 部分完全分开，并将两者的语法连接起来。