我目前正在讨论CFG并看到答案，我不确定他们是如何得到它的。他们是如何让它从CFG转换成正则表达式的？
S -> aS|bX|a
X -> aX|bY|a
Y -> aY|a
answer:
R.E -> (a*(a+ba*a+ba*ba*a))
您应该学习我在答案"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）。
如果您注意到start-variable的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的生产规则替换sentential form bX中的X，并且我们知道X也不可为空，因此总会有一些符号（s） ）在'b'之后 - 换句话说来自bX的感情来源于＆mid;ω＆mid; ＆GEQ; 2。
从上面的讨论形式来看，很明显，使用S生成规则，您可以分两步生成a*a或a*bX的句子形式：
a*反复使用S → aS将给S ⇝ a*S（符号和zigrarr;意味着不止一个步骤）S或S ⇝ a*S替换a*a的rhs中的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 + bX)中给出的正则表达式，你将获得：
S ⇝ a*(a + b X )S ⇝ a*(a + b (a*(a + bY)) )
而现在，最后的Y生产规则相对来说非常简单 - 只需用来创建“加上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)
✎：＆plus;在正式语言中的正则表达式中使用两种语法（i）＆plus;作为二元运算符的意思 - “联合运算”（ii）＆plus;作为一元上标运算符意味着 - “加上clouser” ✎：在编程语言中的正则表达式+仅用于“加上缓冲区” ✞：在正则表达式中我们使用＆mid;联盟的符号，但这不是一个联盟运营商。在联合（A∪B）与（B∪A）相同，但在正则表达式（A＆mid; B）可能不等于（B＆mid; A）