如何找到上下文无关语法的语言？

Question

我无法根据给定的上下文无关语法确定语言。我已经得到提示，该语言有两个部分，但无法弄清楚。

G= ({S,A,B,C,D,E,Z},(0,1),R,S),

S→E|Z
E→A|C 
A→01B|0A|e
B→1B|10A 
C→10D|1C|e
D→01C|0D 
Z→0Z1|e

e 是空字符串。我发现如果它是 Z，0 和 1 的数量是相等的，但无法弄清楚如果它转到 E

Answer 1

有点跑题了，但是您可以很容易地将语法分解成可以独立分析的子语法。

首先，E 规则只出现在 RHS 的一个地方，所以你可以简单地替换它并通过制作 S 规则 S→A|C|Z 来摆脱它。这些非终结符中的每一个都导致一个独立的子语言（语言 A 仅包含 A 和 B 的规则，语言 C 仅包含 C 和 D，以及语言Z 仅 Z。您的语言 G 只是这三种子语言的结合。

语言 A 是平凡规则的（由于所有非终结符都位于规则 RHS 的末尾），并且可以平凡地转换为 2 状态 E-NFA，从而简化为正则表达式 (0|011 *10)*

语言 C 类似地简化为正则表达式 (1|100*01)*

语言 Z 是唯一的非常规子部分，并且是语言 { 0ⁱ1ⁱ |我≥ 0}

这三者的结合就是语言 G，除了语法之外，没有任何特别好的描述方式。