形式语言定义
Howard Yin 2020-11-07 13:20:04 数学形式语言与自动机形式语言计算理论
计算理论的核心问题:计算机的基本能量和限制是什么
- 可计算性:哪些问题可以通过计算解决
- 计算复杂性:解决可计算的问题需要多少资源
- 自动机理论:为了研究计算,要使用哪些计算模型
- 图灵机
- 有限状态机
- 文法、下推自动机
# 形式语言定义
- 符号a、b、c、......
- 字母表Σ、Γ、......:符号的非空集合
- 字符串w、x、y、......:由字母表中的符号组成的有穷序列
- 空串ε:有0个字符的字符串
# 字符串的连接xy:字符串首尾相接得到新字符串
递归地定义字符串的连接:
xy={x(xz)ay=εy=za
其中,a∈Σ、x、y、z是Σ中的符号组成的字符串。
含义:
- 字符串与空串的连接等于其自身
- 如果字符串y等于字符串z与符号a的连接,那么x与y的连接等于x与z的连接与字符a的连接
# 字符串的长度∣w∣:字符串中的符号所占的个数
递归地定义字符串长度:
∣w∣={0∣x∣+1w=εw=xa
其中,a∈Σ、x是Σ中的符号组成的字符串。
含义:
- 空串为0
- 如果字符串w等于字符串x与符号a的连接,那么w长度等于x的长度加一
# 字符串x的n次幂:将字符串重复n次
递归地定义字符串的幂:
xn={εxn−1xn=0n>0
其中,n∈N+、x是Σ中的符号组成的字符串。
含义:
- 字符串的0次幂等于空串
- 字符串的n>0次幂等于这个字符串的n−1次幂与它自身的连接。
# 字符串集合A和B的连接:将两集合中的字符串两两连接
AB={w∣w=xy∧x∈A∧y∈B}
注:由于字符串的连接不满足交换律,字符串集合的连接也不满足交换律。
# 字符串集合A的n次幂:将集合与自身重复连接n次
递归地定义字符串集合的幂:
An={{ε}An−1An=0n>0
含义:
- 字符串集合的0次幂等于只有一个空串的集合
- 字符串集合的n>0次幂等于这个字符串集合的n−1次幂与它自身的连接。
# 性质
若Σ为字母表,则Σn为Σ上长度为n的字符串集合。
# 集合的克林闭包
集合Σ的克林闭包Σ∗定义为:
Σ∗=i=0⋃∞Σi
克林闭包可以用于定义字母表的克林闭包和字符串集合的克林闭包,因为字母表和字符串集合都是集合。
# 字母表Σ上的语言L
L⊆Σ∗
注:关于语言,唯一重要的约束就是字母表必须是有穷的。
# 性质
∅和{ε}都是任意字母表上的语言。
# 集合的正闭包
字母表Σ的正闭包Σ+定义为:
Σ+=i=1⋃∞Σi
正闭包可以用于定义字母表的正闭包和字符串集合的正闭包,因为字母表和字符串集合都是集合。
# 性质
- 字母表的克林闭包等于其正闭包与由一个空字符串组成集合的并集。
- 字符串集合的克林闭包等于其正闭包与由一个空字符串组成集合的并集。
Σ∗=Σ+∪{ε}