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

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

您应该学习我在答案"constructing an equivalent regular grammar from a regular expression"中编写的基本规则，这些规则将帮助您将“正则表达式转换为右或左线性语法”或“将右或左线性语法为正则表达式”-两者都转换。

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

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

正如我在链接的答案中所说的那样，语法规则:S → eS | e与“plus clouser”相对应，并生成字符串e+。同样，您有三对这样的规则可以在语法中生成a+。

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

(注意: a+也可以写成 a*a或 aa* –描述一个或多个 'a'。)

还要注意语法，您没有任何“空产生”，例如 A → ∧，因此 S， X或 Y变量中的任何一个都不是可为空的，这意味着空字符串不是语法语言的成员，例如:ε∉L(G)。

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

S → aS | bX | a

那么很明显，语言中的字符串ω可以以符号 'a'或 'b'开头(因为您有两种选择来应用 S产生式:(1)赋予 S → aS | a作为ω中第一个符号的 'a'，或者(2)用于生成以 S → bX符号开头的字符串)。

现在，L(G)中可能的最小长度字符串ω是多少？ –最小长度的字符串是 'b'，可以使用生产规则 "a"。

接下来请注意 S → a∉L(G)，因为如果您使用 "b"，那么稍后您必须使用 S → bX的某些生产规则来替换 sentential form X中的 bX，并且我们知道 X也不能为空，因此总会有一些符号 X之后的(s)–换句话说，从 'b'得出的∣ω∣≥2。

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

对于a*bX，请重复使用a*，这将给出S → aS(符号⇝表示一个以上的步骤)

将S ⇝ a*S的rhs中的S替换为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))中的 X替换 (a*(a + bY))，您将获得:

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

现在，最后一个 S ⇝ a*(a + bX)的生产规则相对来说非常简单-仅用于创建“plus clouser”的 Y(或 a+)。

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

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

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

✎ : +形式语言中的正则表达式+使用两种语法(i)+作为二元运算符表示–“联合运算”(ii)+作为一元上标运算符表示–“加clouser”
oji :在正则表达式中以编程语言+仅用于“plus clouser”
oji :在正则表达式中，我们使用∣符号表示并集，但这并不完全是联合运算符。并集(A∪B)与(B∪A)相同，但在正则表达式(A ∣ B)中可能不等于(B ∣ A)