有人可以帮我将语法转换为正则表达式吗

Question

有人可以帮我将语法转换为正则表达式并解释如何在一些复杂的语法上进行转换吗？

S -> aA | bB
A -> aC | bC | a | b
B -> aC | bC | a | b
C -> aA

Answer 1

你的这个语法：

S -> aA | bB
A -> aC | bC | a | b
B -> aC | bC | a | b
C -> aA

恰好是右正则文法。因此，它描述了一种常规语言，可以很容易地转换为确定性有限自动机：

q    s    q'
S    a    A
S    b    B
A    a    (C)
A    b    (C)
B    a    (C)
B    b    (C)
(C)  a    A
(C)  b    [D]
[D]  a    [D]
[D]  b    [D]

这里，S是初始状态，C是接受状态，D是死亡状态。要得到一个正则表达式，把这个自动机当作一个NFA，开始用消除状态的正则表达式替换符号标签：

S = aA + bB
A = aC + bC + a + b
B = aC + bC + a + b
C = aA + bD
D = aD + bD

请注意 D = aD + bD = (a + b)D 只有在 D = {} 时才为真。改写：

S = aA + bB
A = aC + bC + a + b
B = aC + bC + a + b
C = aA

现在我们可以通过替换安全地消除 C:

S = aA + bB
A = aaA + baA + a + b = (aa + ba)A + (a + b)
B = aaA + baA + a + b = (aa + ba)A + (a + b)

现在我们可以使用规则 Z = xZ + y => Z = x*y:

S = aA + bB
A = (aa + ba)*(a + b)
B = aaA + baA + a + b = (aa + ba)A + (a + b)

现在替换：

S = aA + bB
A = (aa + ba)*(a + b)
B = (aa + ba)(aa + ba)*(a + b) + (a + b)

现在又是：

S = a(aa + ba)*(a + b) + b((aa + ba)(aa + ba)*(a + b) + (a + b))

现在我们可以对类似的术语进行分组：

S = (a(aa + bb)* + b(aa + ba)(aa + ba)* + b)(a + b)

请注意 b(aa + ba)(aa + ba)* + b 可以因式分解 b((aa + ba)(aa + ba)* + e) 并且 (aa + ba)(aa + ba)* + e = (aa + ba)*:

S = (a(aa + bb)* + b(aa + ba)*)(a + b)

我们可以再次分解：

S = (a + b)(aa + ba)*(a + b)

最后一个表达式对于您的语言来说是一个很好、简洁、正确的正则表达式。它基本上编码了想法 "see one symbol, then see another symbol, but if you see a third symbol it had better not be a b".

Can someone help me Convert Grammar to regular expresion