【编译原理】正则语言和表达式

ゝ一纸荒年。 2023-09-24 17:45 8阅读 0赞

### 正则语言和表达式 ###

*  正则语言
 *  正则表达式：定义正则语言
 *  一些相关的基本概念
 *  基本概念和术语
 *  正则操作
 *  正则表达式：语法
 *  其他一些正则表达式
 *  正则表达式的限制
 *  语言和正则表达式的关系
 *  DFSM, NFSM, 正则语言, 正则表达式
 *  证明语言的非正则
 *  证明语言的正则的方法

# 正则语言 #

DFSM和NFSM是等效的，我们将在方便的地方使用“FSM"。

FSM可以识别正则语言。

能用正则语言表述 《=》 对应的有限状态机

![在这里插入图片描述][5db725edc75c4ebfb6fc0b83bc2eab94.png]

# 正则表达式：定义正则语言 #

每个正则表达式都等效于FSM：

1.  对于任何正则表达式，都存在一个识别正则表达式定义的语言的FSM。
2.  反之亦然：对于任何FSM，都存在定义FSM所识别语言的正则表达式。

由于FSM所识别的语言是正则的，因此，如果某个正则表达式对其进行了描述，那么语言就是正则的。

能够被FSM识别的语言一定是正则的。

语言是正则的《=》能用正则表达式描述它

# 一些相关的基本概念 #

**正则表达式**：表示字符串的**模式**。

正则表达式r完全**由它匹配的字符串集定义**。

集合称为r的语言，写为**L（r）**

集合元素称为**符号**

这组法律符号称为**字母表**，并写成希腊符号∑

# 基本概念和术语 #

字母表：一组非空有限元（符号）（例如\{a, b, c, +, .\}）

字符串：任何有限的符号序列 （集合中的symbols）  
![在这里插入图片描述][5f2ee55d7c734467b4028f0dbfb02bb9.png]

# 正则操作 #

**Union**（并集）：备选方案的选择，由元字符“|”或“∪”表示。  
![在这里插入图片描述][245c97e478a74930a313efc098767b94.png]  
**Concatenation**（连接）：由并列表示“○”  
![在这里插入图片描述][6b8b015ad2f045ffbee613d2b5ab5b57.png]  
**Repetition**（重复）或 **“closure”**（结束），由元字符“\*”表示  
![在这里插入图片描述][8a792c5395484632842c1320917e901e.png]

# 正则表达式：语法 #

语法：合法表达式  
设∑为字母表。表达式R是正则的，如果R是以下表达式之一：

1.  对于∑中的某个a
2.  元字符ε（空字符串）
3.  Φ（空语言）
4.  R1 ∪ R2 其中R1和R2都是正则表达式
5.  R1 ○ R2 其中R1和R2都是正则表达式
6.  R\*，其中A是正则表达式

# 其他一些正则表达式 #

R+表示R*中具有非零长度的所有字符串的集合  
R+ ∪ ε = R*

# 正则表达式的限制 #

每一种有限语言都是正则的。

只有无限语言可以是非正则的，但并非所有无限语言都是非正则语言。

# 语言和正则表达式的关系 #

不是所有的语言可以用正则表达式表达出来。

不是所有的语言可以写成正则语言。

# DFSM, NFSM, 正则语言, 正则表达式 #

DFSM和NFSM等效

1.  每个DFSM都是NFSM
2.  每个NFSM都可以转换为DFSM

FSM识别的语言（无论是确定性的还是非确定性的，因为它们是等价的）是正则的

正则表达式可用于定义语言

正则表达式等效于FSM

1.  对于每个正则表达式，都有一个等效的FSM。
2.  对于每个FSM，都有一个等价的正则表达式。
3.  这意味着由正则表达式定义的语言是正则的，并且每个正则语言都有一个正则表达式。

# 证明语言的非正则 #

Interesting languages are nonregular （其中一些属于上下文无关语言类）

我们研究、证明并应用抽运引理作为证明语言非正则性的一种方法 （规则背后的直觉：无限语言有一些重复的结构）

# 证明语言的正则的方法 #

1.  每个有限语言都是正则的
2.  给出正则表达式
3.  提供FSM
4.  使用闭包性质

***Thanks to Dr. John: Some contents are from their slides.***

[5db725edc75c4ebfb6fc0b83bc2eab94.png]: https://img-blog.csdnimg.cn/5db725edc75c4ebfb6fc0b83bc2eab94.png
[5f2ee55d7c734467b4028f0dbfb02bb9.png]: https://img-blog.csdnimg.cn/5f2ee55d7c734467b4028f0dbfb02bb9.png
[245c97e478a74930a313efc098767b94.png]: https://img-blog.csdnimg.cn/245c97e478a74930a313efc098767b94.png
[6b8b015ad2f045ffbee613d2b5ab5b57.png]: https://img-blog.csdnimg.cn/6b8b015ad2f045ffbee613d2b5ab5b57.png
[8a792c5395484632842c1320917e901e.png]: https://img-blog.csdnimg.cn/8a792c5395484632842c1320917e901e.png