context-free-grammar - 语法到正则表达式

Question

找到接受给定语法的相同语言的正则表达式的过程步骤是什么？

• S --> b | AA
• 一个--> aA | 艾伯 | ε

Answer 1

我正在写一些试图理解的东西（希望它会有所帮助）：

1. 根据S --> b，字符串 'b'是语法语言中的字符串。

2. 使用A's 产生 式A --> aA | & ，我们可以生成：“A后跟任意数量的as”，或者在 RE 中：a*A （* 因为 epsilon）

3. 同样，使用 A ---> Abb | & 我们可以生成“任意数量的bbs 后跟A”，或者在 RE: A(bb)*(* 因为 epsilon)

4. 使用 2 和 3A可以生成： a*(bb)*

5. 请注意，最终变量必须转换为终端，因此 A 可以转换为a,bb或&。

6. 从 4 开始，使用 AA我们可以生成： a*(bb)*a(bb)*.

所以在语法生成的语言中是b + a*(bb)*a(bb)*

对于程序，请阅读此答案：Constructing an equivalent Regular Grammar from a Regular Expression我从 RE 到语法的解释，我觉得该答案将帮助您更好地理解。

Answer 2

语法：

• S --> AS|a

• A --> SA|b

  1. 根据 S --> a，字符串 a 是语法语言。
  2. 根据 A --> b，字符串 b 是语法语言。
  3. 使用 A --> SA，我们可以生成 A-->SA ；A-->SSA ; A-->SSSA ; ...
  4. 使用 S --> AS，我们可以生成 S-->AS ；S-->原子吸收光谱法；S-->AAAS ; ...

我怎样才能达到这个语法的正则表达式和解决方案？

---

这些规则有用吗？

• x=yx+t 解是 y*t
• x=xy+t 解是 ty*

S=AS+a；A=SA+b

S=A*a ; A=S*b

---

从 A=SA+b 和 S=AS+a

• 我得到 A=S*b 和 S=S*bS+a
• 所以我得到 S=(S*b)*a
• S=(a*b)*a

正确@GrijeshChauhan ??