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

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

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


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

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

不过，一种语言可以有多个正则表达式（和语法/自动机）。下面，我尝试解释如何查找教科书中问题的答案中给出的正则表达式。准确阅读每个步骤和链接的答案，以便您下次可以学习解决此类问题的方法。

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

As I said in linked answer, grammar rules like: S → eS | e are corresponding to "plus clouser" and generates strings e+. Similarly, you have three pairs of such rules to generate a+ in your grammar.

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

(Note: a+ can also be written as a*a or aa* – describes one or more 'a'.)

另请注意，在语法中，您没有任何“空产生式”，例如A → ∧，所以非变量S, X or 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 in 句子形式 bX使用一些X的产生式规则，正如我们所知X也不能为空，因此后面总是有一些符号'b'——换句话说，是感伤的bX推导∣ω∣ ≥ 2.

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

1. For a* use S → aS重复这将给S ⇝ a*S（符号∽表示多一步）

2. Replace S右旋S ⇝ a*S得到要么通过a*a or a*bX

Also, "a*a or a*bX" can be written as S ⇝ a*(a + bX) or S ⇝ (a*(a + bX)) if you like to parenthesizes complete expression^✎.

现在比较一下生产规则S and X两者都是一样的！正如我上面所示S，您还可以描述X它可以用来生成句子形式X ⇝ (a*(a + bY)).

导出答案中给出的正则表达式替换X by (a*(a + bY)) in S ⇝ a*(a + bX)， 你会得到：

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

And now, last Y production rules are comparatively very simple - just use to create "plus clouser" a+ (or a*a).

所以让我们替换Y也在S派生句子形式。

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

Simplify it, apply distribution low twice to remove inner parenthesis and concatenate regular expressions – P(Q + R) can be written as PQ + PR.^✞

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

✎ ^{: + in regular expression in formal languages use in two syntax (i) + as binary operator means – "union operation" (ii) + as unary superscript operator means – "plus clouser"}
✎ ^{: In regex in programming languages + is only uses for "plus clouser"}
✞ ^{: In regex we use ∣ symbol for union, but that is not exactly a union operator. In union (A ∪ B) is same as (B ∪ A) but in regex (A ∣ B) may not equals to (B ∣ A)}