正则表达式、(正则)文法和语言的转换关系

发表于 | 分类于

1. 正则表达式，语言以及正则文法的转换关系

  • 语言：一种映射关系，合法字符串集合。
  • 文法：一个四元组$(T, NT, S, P)$，分别表示终结符，非终结符，起始符号和产生式。
  • 正则定义(正则表达式)均能用正则文法表示。

1.1. 文法转语言

1
2
3
4
5
6
7
A -> abc
A -> aBbc
Bb -> bB
Bc -> Cbcc
bC -> Cb
aC -> aaB
aC -> aa

分析可以发现先B移到第一个c的前面，变为Cbc。然后，C移到最后一个a的后面，变为aB。因此，表示的语言为abc, aabbcc, aaabbbccc…，即$\{a^nb^nc^n\|n>=1\}$

1.2. 语言转文法

p1: 有语言$L(G[s])=\{a^mb^n\|n>m>0\}$

注意到b的数量比a大，且a的数量大于0。可以提取公因式$(ab)^mb^{n-m}$。

1
2
3
4
5
6
7
8
// 单独生成b的k(k>0)次的文法
S -> Sb
  |  b
// 因此可以得到文法如下
S -> Sb // 保证b数量比a可以多>=2
  |  Ab // 保证b数量比a至少多1
A -> aAb
  | ab

p2: 有语言$\{a^nb^nc^m\|n>=1, m>=0\}$

n和m没有直接关系，但是ab需要出现相同次，且次数大于等于1

1
2
3
4
S -> abS // 保证n可以>=2
   | abA // 保证n>=1
A -> mA
   | ε

2. 正则文法转正则表达式

问：给定正则文法G，构造一个正则表达式r，使得L(r)=L(G).

  • 设正则文法是右线性的，且其每个产生式右部只有一个终结符，则通过以下方式构造方程式。

re-grammar1.png

  • 自底向上代入消元法消除方程组中除S外其它变量即得到正则表达式。

re-grammar2.png

2.1. 示例

存在文法G如下，转换为对应的正则表达式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
S -> aS
   | aB
B -> bB
   | bC
   | aB
   | bS
C -> cC
   | c
// 列出方程式
S = a*S
S = aB
B = (a|b)*B
B = bC
B = bS
C = c*C
C = c
// 带入消元
C = c*c|c
B = (a|b)*(bc*c|bc)
B = (a|b)*bS
S = a*aB
S = (a*a(a|b)*bS)|(a*a(a|b)*(bc*c|bc))
S = (a*a(a|b)*b)*a*a(a|b)*(bc*c|bc)

3. 正则表达式转正则文法

问：给定正则表达式r，构造一个正则文法

正则表达式转正则文法.png

  • 若能直接或运算，则把能或运算的全部打开
  • 若能直接无符号终结符关联，则引入新非终结符处理关联运算的第二部分
  • 若直接为闭包结构，则构建出对自身的引用

3.1. 示例

对于闭包结构正则表达式$(0\|1)*$，可以利用循环定义

1
2
3
4
S -> (0|1)*
  -> (0|1)+ | ε
  -> (0|1) (0|1)* | ε
  -> 0S | 1S | ε

对正则表达式$(a\|b)*a(a\|b)(a\|b)$

1
2
3
4
S -> Aa | Ab
A -> Ba | Bb
B -> Ca
C -> aC | Cb | ε