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

Question

我无法从给定的上下文无关语法中确定语言。我已经得到了一个暗示，该语言有2个部分，但无法想出来。

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是唯一的非常规子部分，是语言{0i1i |我和我的0}

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