当前课程知识点：软件理论基础 > 第一章 基础知识 > 1.6 语言运算 > Video
欢迎同学们来到《软件理论基础》Mooc课堂
现在介绍第六节
语言及语言的运算
语言是这门课中重要的内容
什么是语言呢?
上一节介绍了字母表
以及字母表的“*”闭包
一个字母表 ∑
它的“*”闭包中的任何一个子集 L
L 包含在 ∑* 中
那么，我们称 L 为 ∑ 上的一个语言
定义简单
“*”闭包中的任何一个子集
都是 ∑ 上的一个语言
下面看
给了字母表 {a,b}
“*”闭包是 ∑ 中字母 a、b 的
任何有限串构成的集合
{ε} 是它的语言
{a,aa,aab} 是它的语言
还有{ε,abba,……}，等等，这些都是它的语言
可以看出，语言中一个
特点是集合
它是 ∑* 中的一个集合
谈到语言时
语言就是一个集合
看一个特殊的集合--空集
空集跟空串是不一样的
空集是一个集合，它是语言
而空串是语言中一个元素
空集用 φ 表示
也可以用大括号{}
这里面没有任何元素，来表示
如果一个集合包含了空串，那这个集合
可以表示一个语言
它跟空集是不一样的
单个空串ε不是集合
它不是语言
这个集合
它元素的个数
空集 φ 元素个数等于 0
而这个集合包含一个元素ε空串
所以，这个集合元素个数等于 1
但是，如果是串，串它有长度
空串长度等于 0
大家从这几个表示
能够分清空集与空串之间的差异
另外一个例子
这是字母表 {a,b} 上的一个集合
集合的元素是 a^nb^n
上节，大家清楚
这是字母表 {a,b} 上的一个语言
它是一个无限语言
ab 是这里的元素
是它的串
aabb 是这里的元素
aaaaabbbbb
是满足这个性质的串
也是这里的元素
它们都属于 L 的
哪些不属于 L 呢？
譬如，abb 不满足这个性质
所以这个串就不在这里面
我们给了语言
就有语言的一些运算
首先，我们知道语言是一个集合
集合本身有运算的
集合有哪些运算？
像集合有“并”运算
“交”运算、“差”运算
在语言里，有“并”运算、“交”运算、“差”运算
还有语言的“补”运算
语言的补运算，等于 ∑* 减去这个集合
得到的集合
语言除了这些运算之外
因为语言本身有自己的特征
它是字符串构成的集合
那语言自己还有一些运算
譬如，给了语言 L
语言的反转，怎么定义呢？
这个语言中每一个串都做反转
得到的集合叫做原来语言的反转
给了{ab, aab, baba}
这个语言的反转是每一个串
都作反转得到的语言
刚才介绍了语言
a 的 n 次方 b 的 n 次方
反转就是 b 的 n 次方 a 的 n 次方
语言另外一个运算
语言的连接
上一讲介绍了串的连接
语言的连接，给了两个语言
L1、L2，它们的连接，把 L1 中的串
作为前缀
L2 中的串作为后缀
它们连接得到新的串构成的集合
叫 L1 和 L2 的连接
譬如，{a, ab, ba} 是一个语言
{b, aa} 是另外一个语言
把这个语言里的元素作前缀
这个语言的元素作后缀
它们组成新的一些串
就得到这个语言
这语言就是这两个语言的连接
在连接运算内
如果这些语言都相同的话
我们定义语言的幂运算
这 n 个语言
它们的连接得到 L 的 n 次方
{a, b} 可以看作是字母表
同时，它也是一个语言
这是一个集合
它的三次方等于这个语言的三次连接
就得到这样的语言
在语言的幂运算
我们定义 L 的 0 次方
L 的 0 次方，也表示一个语言
只包含空串的一个语言
譬如，这个语言的零次方
等于 {ε}
另外一个例子
给了这个语言，是刚才介绍的
它的平方等于 a 的 n 次方
b 的 n 次方
a 的 m 次方
b 的 m 次方
n 和 m 是任意的，这样的串构成的集合
就是这个语言的平方
语言的闭包运算
首先介绍，给了一个语言 L
它的“*”闭包，也叫 Kleene 闭包
是这个语言的 0 次方
与这个语言的 1 次方
与这个语言的 2 次方，……，等等
无穷的语言序列“并”起来
叫做 L 的 kleene 闭包
{a, bb} 这个语言
它的“*”闭包包含哪些元素？
空串、a、bb
还有这些
还有这些，等等，是一个无穷的 L 的集合
这是语言的 Kleene 闭包
“正”闭包，它是语言 L 的
一次方、二次方、三次方、……，等等
无穷序列
由这无穷的序列“并”起来，构成的一个集合
用 L^+ 表示
也叫 L 的正闭包
L 的“正”闭包，实际上是
原来 L 的 Kleene 闭包
去掉空串得到这语言（严格地讲，L 不包含空串）
下面看
刚才给的语言
它的“正”闭包，是这样得到的集合
实际上是原来给的
“*”闭包除掉空串
这一章我们介绍了
这门课用到的一些基本知识
一些数学基本知识
图的一些知识
一些证明方法
还有语言的一些基本的概念、基本的运算
这是后面知识一些基础
这节内容介绍完毕
谢谢大家！
-1.1 概要
--第一节
-1.2 数学基础
--Video
-1.3 图
--Video
-1.4 证明方法
--Video
-1.5 语言基础
--Video
-1.6 语言运算
--Video
-习题--作业
-2.1 确定有限自动机的概念
--Video
-2.2 确定有限自动机的定义
--Video
-2.3 扩展转移函数
--Video
-2.4 正则语言
--Video
-2.5 DFA构造
--Video
-习题--作业
-3.1 非确定有限自动机的概念
--Video
-3.2 e转移
--Video
-3.3 非确定有限自动机的定义
--Video
-3.4 扩展转移函数
--Video
-3.5 等价性证明
--Video
-3.6 文本搜索
--Video
-习题--作业
-4.1 单一终结状态的NFA
--Video
-4.2 正则语言的运算性质
--Video
-4.3 正则表示和语言
--Video
-4.4 正则表示和正则语言
--Video
-4.5 正则语言的同态
--Video
-4.6 正则表示的代数定律
--Video
-习题--作业
-5.1 文法
--Video
-5.2 线性文法
--Video
-5.3 正则文法与正则语言
--Video
-5.4 自动机的积
--Video
-习题--作业
-6.1 基本问题
--Video
-6.2 泵引理
--Video
-6.3 非正则语言的判定 1
--Video
-6.4 非正则语言的判定 2
--Video
-6.5 DFA的优化 1
--Video
-6.6 DFA的优化 2
--Video
-习题--作业
-7.1 上下文无关文法
--Video
-7.2 规约和推导
--Video
-7.3 语法分析树
--Video
-7.4 规约、推导和语法分析树之间的关系
--Video
-7.5 上下文无关语言
--Video
-习题--作业
-8.1 CFG的应用
--Video
-8.2 CFG的转化
--Video
-8.3 文法二义性
--Video
-8.4 二义性的消除方法
--Video
-8.5 CFG的构造方法
--Video
-8.6 CFG的构造实例
--Video
-第八章 CFG的应用与文法的二义性--习题
-9.1 PDA介绍
--Video
-9.2 PDA的定义
--Video
-9.3 PDA的即时描述
--Video
-9.4 PDA的语言
--Video
-9.5 PDA与CFG的关系
--Video
-习题--作业
-10.1 确定下推自动机
--Video
-10.2 DPDA与其他语言的关系
--Video
-10.3 终态型DPDA和空栈型DPDA
--Video
-10.4 消除无用符号
--Video
-10.5 消除e产生式
--Video
-10.6 消除单一产生式
--Video
-10.7 CFG的化简与Chomsky范式
--Video
-习题--作业
-11.1 CFL的必要条件
--Video
-11.2 CFL的Pumping引理
--Video
-11.3 CFL的闭运算性质
--Video
-11.4 CFL的同态性质
--Video
-11.5 CFL的交运算
--Video
-11.6 CFL的判定性质
--Video
-习题--作业
-12.1 图灵机的介绍
--Video
-12.2 图灵机的定义
--Video
-12.3 图灵机的即时描述
--Video
-12.4 图灵机的计算
--Video
-12.5 图灵机的编程技术
--Video
-习题--作业
-13.1 Turing理论
--Video
-13.2 图灵机带的扩展
--Video
-13.3 图灵机移动的扩展
--Video
-13.4 受限图灵机
--Video
-13.5 图灵机与其他自动机
--Video
-习题--作业
-14.1 图灵机编码
--Video
-14.2 对角线语言与通用语言
--Video
-14.3 图灵机语言的性质
--Video
-14.4 判定问题和语言
--Video
-14.5 计算复杂性问题
--Video
-第十四章 不可判定问题--习题
-15.1 时间自动机
--Video
-15.2 Buchi自动机
--Video
-15.3 软件形式化验证
--Video
-15.4 模型检测方法
--Video
-15.5 M3C模型检测系统
--Video
-习题--作业
-期中考试
