将上下文无关的语法转换为正则表达式

Question

我目前正在浏览CFG，看到了答案，但不确定他们是如何得到的。他们是如何在这里将其从CFG转换为正则表达式的？

S -> aS|bX|a
X -> aX|bY|a
Y -> aY|a


answer:
R.E -> (a*(a+ba*a+ba*ba*a))

Answer 1

您应该学习我在答案“从正则表达式构造等效的正则语法”中编写的基本规则，这些规则将帮助您将“正则表达式转换为右或左线性语法”或“右或左线性语法”语法转换成正则表达式”-两者皆有。

但是，一种语言可以使用多个正则表达式（和语法/自动机）。下面，我试图解释如何找到教科书中该问题答案的正则表达式。仔细阅读每个步骤并链接答案，以便您下次可以自己学习解决此类问题的方法。

第一步，要回答这样的问题，您应该清楚“该语法产生什么语言？” （类似地，如果您拥有自动机，则尝试理解该自动机所代表的语言）。

正如我在链接答案中所说的那样，语法规则如：S → eS | e对应于“ plus clouser”并生成string 。同样，您在语法中要生成三对这样的规则。e+a+

S → aS | a   
X → aX | a  
Y → aY | a    

（注意：也可以写为或–描述一个或多个。）a+a*aaa*'a'

另请注意，在语法中，您没有任何“空产生”，例如A → ∧，因此不是的变量S，X或者Y是可为空的，表示空字符串不是语法语言的成员，例如：ε∉L（G）。

如果您注意到起始变量的S生产规则：

S → aS | bX | a

然后，它很清楚，串在语言ω可以用符号开始'a'或'b'（如你有两个选择申请S制作：（1）S → aS | a给出'a'的第一个符号的ω，或（2）S → bX在使用生成一个字符串的开始带有符号'b'）。

现在，L（G）中可能的最小长度字符串ω是多少？–最小长度的字符串是"a"使用生产规则可能的 S → a。

接下来要注意"b"∉L（G），因为如果您是苹果用户，S → bX那么以后您必须使用的某些生产规则X以句子形式 替换，并且我们也知道它也不可以为空，因此在– 之后总会有一些符号–换句话说，感生自ωω≥2。 bXXX'b'bX

在上面的讨论中，很明显，使用S生产规则，可以分两个步骤生成a*a或的句子形式a*bX：

1. 对于a*使用S → aS多次，这将使S ⇝ a*S （符号⇝手段不止一个步骤）

2. 替换S在RHS S ⇝ a*S由获得任意a*a或a*bX

另外，“” a*a或a*bX“”可以写成，S ⇝ a*(a + bX)或者S ⇝ (a*(a + bX))如果您想在完整的表达式圆括号内^加上。

现在比较的生产规则，S并且X两者相同！因此，正如我上面显示的S，您还可以为此描述X它可以用来生成句子形式X ⇝ (a*(a + bY))。

要派生在answer中替换X为(a*(a + bY))in 的正则表达式S ⇝ a*(a + bX)，您将获得：

S ⇝ a*(a + b X )  
S ⇝ a*(a + b (a*(a + bY)) )

现在，最后的Y生产规则相对来说非常简单-只需创建“ plus clouser” （或 ）即可。a+a*a

因此，让我们Y也以S派生的句子形式替换。

S ⇝ a*(a + b(a*(a + bY)))   
  ⇝ a*(a + b(a*(a + ba*a)))

简化它，将分布较低的值两次应用以消除内部括号并连接正则表达式– P(Q + R)可以写成PQ + PR。^✞

  ⇝ a*(a + b(a*(a + ba*a)))     
  ⇝ a*(a + b(a*a + a*ba*a))     
  ⇝ a*(a + ba*a + ba*ba*a)

✎ ^{： +在形式语言中的正则表达式中使用两种语法（i）+作为二元运算符表示–“联合运算”（ii）+作为一元上标运算符表示–“加clouser”}
✎ ^{：在regex中以编程语言表示+仅对于“加clouser”用途}
✞ ^{：在正则表达式，我们使用|符号工会，但就是不完全是一个联合运营。并集（A∪B）与（B∪A）相同，但在正则表达式（A ∣ B）中可能不等于（B ∣ A）}