正规式和正则表达式的异同

正规式的定义及使用方法(转自正规式)

设∑是有穷字母表，并定义辅助字母表∑’={Φ, ε, | , . , *, (, )}

1. ε,Φ都是∑上的正规式，它们所表示的正规集为{ε}, Φ ;
2. 任何a是一个正规式，若a∈∑，它所表示的正规集为{a}；
3. 如果R₁和R₂是正规式，它们表示的正规集分别为L₁和L₂，则 R₁|R₂ , R₁·R₂ , R₁^* , (R₁) 也是正规式，并且它们所表示的正规集分别为L₁∪L₂ ；L₁L₂；L₁^* ； L₁
4. 仅有有限次使用上述三步骤而定义的表达式才是∑上的正规式，仅有这些正规式表示的字集才是∑上的正规集。

注意：不要混淆Φ和ε，正规表达式ε描述的语言只含一个空字符串ε，而Φ表示的语言不含有任何字符串。 程序设计语言的单词都能用正规式来定义。若两个正规式e₁,e₂表示的正规集相同，则称它们等价。记作:e₁=e_2。