编译原理 —— 正规文法转换为正规式

  • 正规文法与正规式都是描述正规集的工具。对任意一个正规文法，存在定义统一语言的正规式；反之，对每个正规式存在一个生成同一语言的正规文法。

  • 对任何正规文法G，存在定义同一语言的正规式 r

求解过程

① 将文法中的规则写成关于每个非终结符的正规式方程，得到一个方程组；

② 依照求解规则：

  • 若 A = α A ∣ β A=αA |β A=αA∣β，则解为 A = α ∗ β A= α^*β A=α∗β；
  • 若 A = A α ∣ β A=Aα |β A=Aα∣β，则解为 A = β α ∗ A= βα^* A=βα∗；

示例

设有正规文法G：

  • A→ aB | bB
  • B→ aC | a | b
  • C→ aB

试给出该文法生成语言的正规式

解：首先给出相应的正规式方程组（方程组中用“+”代替正规式中的“|”）如下：

  • ① A = aB + bB
  • ② B = aC + a + b
  • ③ C = aB

把 ③ 式代入 ② 式得

  • ④ B = aaB + a + b

对 ④ 式使用求解规则得

  • ⑤ B = (aa)*(a + b)

把 ⑤ 式代入 ① 式得

  • ⑥ A = a(aa)* (a + b) + b(aa)* (a + b)