语言{0^m 1^m 2^n | n>=0，m> n}的结果是什么

Question

我想知道如何获取语言{0^m 1^m2^n| n>=0，m> n}的结果。

这就是我所拥有的，我不确定它是否正确。如果我错了，请纠正我：

 S -> 01A | 0B1A | 00B11A
 A -> 2A | 2 | λ
 B -> 01

谢谢。

Answer 1

这种语言不是上下文无关的。这可以使用上下文无关语言的pumping引理来说明。你最终得到了五个案例；其中三个案例只抽取符号0、1或2中的一个；两个案例抽取相邻的符号。请注意，除了我们可以选择字符串0^(p+1) 1^(p+1) 2^p之外，您几乎可以做到这一点，即使当您跨越0和1并均匀地抽取它们时，您仍然无法通过m>n测试。

有比上下文无关更强大的语法。我们可以为这种语言产生一个通用的语法。

S -> RT
R -> 0R1X | 01

X1 -> 1X

XT -> T2 | T
1T -> e

前两个结果生成形式为0^n (01) (1X)^n T的字符串。

第三个结果产生形式为0^n (01) 1^nX^nT的字符串。它允许X向右“浮动”，越过所有的1。

最后两个结果产生形式为0^n (01) 1^n2^m，m<=n的字符串。这些字符串允许T向左“浮动”通过X，将每个X转换为2或为空。