形式语言与自动机理论（哈工大）学习笔记Day02

一、基本概念

1.字母表：符号（字符）的非空有穷集。

Σ₁={0, 1}，这个字母表可以构建所有的二进制数组成的语言

Σ₂={a, b, ... , z}，这个字母表可以构建由小写英文字母组成的语言

Σ₃={x∣x是一个汉字}，这个字母表可以构建汉语这样的语言

2.字符串：由某字母表中符号组成的有穷序列。

若Σ₁={0, 1}，那么0，1，00，111001为Σ₁上的字符串；

若Σ₂={a, b, ... , z}，那么ab，xkcd为Σ₂上的字符串。

3.空串：记为ε，有0个字符的串。

字母表Σ可以是任意的，但都有ε∉Σ。

符号使用的一般约定：

• 字母表：Σ，Γ, ...
• 字符：a，b，c, ...
• 字符串：... , w，x，y，z
• 集合：A，B，C, ...

4.字符串的长度：字符串中符号所占位置的个数，记为∣?∣。

若字母表为Σ，可递归定义为：

其中a∈Σ，w和x是Σ中字符组成的字符串。

w=xa表示将字符串w分割成最后一个字符a和除最后一个字符以外的字符串x，这里推荐自己举例来描述递归的过程。

5.字符串x和y的连接：将首尾相接得到新字符串的运算，记为x·y或xy。

同样，可递归定义为：

·

其中a∈Σ，且x，y，z都是字符串。

空串和任何的字符串，从无论是左边连接还是右边连接，都等于这个字符串本身。

连接运算的“·”一般省略，连接运算满足结合律，不满足交换律。

6.字符串x的n次幂（n≧0），递归定义为：

字符串x的n次幂相当于将字符串x重复n次，因此n=0时，字符串x重复0次，即为空串。

例如，若Σ ={a, b}，那么

7.集合A和B的连接，记为A·B或AB，定义为A·B = {w∣w = x · y, x∈A且y∈B}。

集合的连接运算同样不满足交换律。

8.集合A的n次幂（n≧0），递归定义为：

集合A的n次幂相当于从集合A中选n次字符串组合成新字符串的运算，因此n=0时，从集合A中选0次字符串，组合成空串。

那么，若Σ为字母表，则Σⁿ为Σ上长度为n的字符串集合。

如果Σ ={0, 1}，有

9.克林闭包（Kleene Closure）：

10.正闭包（Positive Closure）：

显然，

二、语言

定义

若Σ为字母表且，则L称为字母表Σ上的语言。

• 自然语言，程序设计语言等
• {0ⁿ1ⁿ}
• The set of strings of 0's and 1's with an equal number of each: {ε, 01, 10, 0011, 0101, 1100, ...}
• 分别都是任意字母表Σ上的语言，但注意

关于语言

对于语言的限制其实是很少的，唯一重要的约束就是所有字母表都是有穷的。

三、问题

自动机理论中的典型问题

判断给定的字符串w是否属于某个具体的语言L，w∈L？

• 任何所谓问题，都可以转为语言成员性的问题
• 语言和问题其实是相同的东西

四、形式化证明：演绎法，归纳法和反证法

例1. 若x和y是Σ上的字符串，请证明

证明：通过对y的归纳来证明。

续例1. 若x和y是Σ上的字符串，请证明

证明：通过对y的归纳来证明。