给出满足L（G）= L的正式语法G.

Question

我在过去的试卷中给了我以下问题。我理解解决方案（有点？），但想知道是否有人知道如何实际生成解决方案（或者更简单的解决方案）。

给出满足L（G）= L的正式语法G ...

L := {w member of {a,b}* | n does not exist in N : w = (ab)^n}

答案是：

G : ({A,B,S},{a,b},P,S) with
P := { 
       S-> a | empty | bA | aB | aaA
       A-> aA| bA | empty
       B-> aB | bB | a | aaA | bbA  }

Answer 1

老问题，但这可能会帮助其他人。

你给出的语言是所有单词的集合，不能写成字符串ab的（可能为空）串联;也就是说，除了(ab)*中的所有单词。

所要求的语言是简单语言的补充，是我们寻找语法的途径。首先，我们可以为(ab)*语言编写DFA：

Q   s   Q'
q0  a   q1
q0  b   q2
q1  a   q2
q1  b   q0
q2  a   q2
q2  b   q2

最初的状态q0是唯一接受的州。 q2是一个死态。

要获得我们想要的语言的DFA，我们可以简单地交换此DFA的接受和不接受状态。也就是说，为了接受包含不能用(ab)^n作为任何自然数n的字符串的语言，我们只需使q1和q2接受而不是q0。

从DFA获取语法非常简单。非终结符号对应于DFA状态。 DFA中的过渡成为语法中的产物。如果您在DFA中的符号q上从状态q'过渡到s，并且非终结符号A和B对应于q和q'，则会在语法中获得生成A := sB。如果q在你的DFA中是一个接受状态而A对应于q，那么你也有一个生产A := e，其中e是空字符串。如果你不想要空制作（除了可能需要的S := e），你也可以通过复制制作来处理接受状态。这是进行施工的一种方式;还有其他一些同样好的。

对于我们的情况：

S ~ q0
A ~ q1
B ~ q2

S := aA      f(q0, a) = q1
S := bB      f(q0, b) = q2
A := aB      f(q1, a) = q2
A := bA      f(q1, b) = q0
B := aB      f(q2, a) = q2
B := bB      f(q2, b) = q2
A := e       q1 is accepting
B := e       q2 is accepting

我们现在可以通过组合线来编写EBNF：

S := aA | bB
A := aB | bA | e
B := aB | bB | e