2-3正规式与正规集

正规式与正规集

定义

• 设∑为有限字母表,在∑上的正规式与正规集可递归定义如下:

  1. ε和Ф是∑上的正规式,它们表示的正规集分别为{ε}和Ф;
  2. 对任何a∈∑, a是∑上的正规式,它的正规集为{a};
  3. 若r,s都是正规式 , 它们的正规集分别为R和S , 则 (r|s)、(r·s)、(r)* 也是正规式,它们分别表示的正规集是:R∪S,RS,R*。

  有限次 使用上述三条规则构成的表达式,称为∑上的正规式,仅由这些正规式表示的集合为正规集。

z.B.
令Σ={ 0, 1 } 则 0,1,ε 和 Ф 是Σ上的正规式

正规式	正规集
0 | 1	{ 0 , 1 }
0 • 1	{ 01 }
1 • 0	{ 10 }
0*	{ ε, 0, 00, 000, … }
1*	{ε, 1, 11, 111, … }
(0|1)0*	{ 0, 1,00,000,…,10,100,1000, … }
(0|1)01	{ 001,101 }

关系

• 正规式与相应的正规集是等价的,正规集给出了相应正规式所描述的全部单词(句子)
• 正规式的运算结果是正规集
• 正规式不是集合,其运算结果正规集是集合 Ф是特例

正规式运算优先级

• 正规式运算优先级从高到低

  () > * > • > |

• 同级运算从左到右

正规式与正规集的表示

• 正规式r所表示的正规集R是字母表∑上的语言,称为正则语言,用 L(r) 表示,即R=L(r)。L(r)中的元素为字符串,称为L(r)的句子。

设PASCAL语言子集有如下单词:
BEGIN , END , IF , THEN , ELSE , 标识符 , 无符号整常数 , > , >= , < , <= , = , < >
正则式描述:

名词	正则式描述
关键字	BEGIN|END|IF|THEN|ELSE
标识符	<字母>(<字母>|<数字>)*
无符号整常数	<数字>(<数字>)*
关系运算符	> | >= | < | <= | = | < >

• 若两个正规式r和s所表示的语言L(r)=L(s) ,则称r, s等价,记为 r=s

  z.B.
  1(01)* = (10)*1

正规式与FA

• 字母表∑上的确定的有限自动机M所接受的语言 L(M)是∑上的一个正规集
• 对于∑上的每一个正规式r,存在一个∑上的非确定有限自动机M,使得:L(M)=L(r)

∑上的单词集V∈∑*是正规的,当且仅当存在∑上的DFA M,使得V=L(M)
证明:

1. <= 若有∑上的NFA M,则L(M) = L(V);
2. => ∑上任何正规式V,存在相应的DFA M,使得L(M) = L(V)。

z.B.

证明1.

拓广NFA M：

1. 增加节点X，并从X引ε弧到达S0中的所有状态
2. 增加结点Y,并从Z中所有状态引ε弧到达Y

设有NFA M 如下图所示：

利用替换规则一逐步消去 M’中的结和弧,并用正规式代替原来M’中的弧标记,直至只剩下XY结为止。

证明2.

由V直接形成拓广的FA状态图。构造∑上的NFA M’,使得L(M’)=L(V)


有V= (a|b)*(aa|bb)(a|b)*


NFA M’确定化