当前课程知识点：软件理论基础 > 第一章 基础知识 > 1.5 语言基础 > Video
欢迎同学们来到《软件理论基础》Mooc课堂
现在介绍第五节
语言基础
语言的构造
首先需要一个字母表
字母表有哪些呢?
譬如，英文字母小写的 a、b、c
大写的 A、B、C，等等
英文标点符号
在这里算是字母表
汉字、化学元素表中符号
都是这里的一些字母表
比如，还有 ∑ = {a，n，y，任意}，等等
都表示字母表
在字母表
我们通常用小写字母 a、b、c 表示它的字母
由字母可以构造字符串
怎么构造呢？
假设给了字母表 ∑ = {a,b}
字母可以重复出现
构成有限的串
像 a、ab、abba、baba，等等
是有限个字母构成的串
叫字符串
这是基于字母构成的串
通常用小写字母 u、v、w
表示字符串
u=ab
v=bbbaaa
w=abba，等等
都是表示字母上的串
有了字符串
就可以讨论字符串的一些运算
假如给了字符串 w = a1a2…an
v 字符串是 b1b2…bn
可以举出具体的串
abba、bbbaaa
字符串的第一个运算
也是前面提到的一个运算
连接运算
是把 w 字符串和 v 字符串
无缝地放在一起
构成了一个新的字符串
譬如，给了这两个具体的字符串
它们的连接得到这新的字符串
这是字符串的第一个运算
假设给了字符串 w
比如说，a1a2…an
具体的一个字符串是这样
给第二个字符串的运算--反转
反转是把原来的字符串
它的顺序完全颠倒
原来 an 放在第 n 个位置
改成第一个
n-2 个，改成第二个位置
一直到 a2，改成倒数第二个
a1 成了最后一个
这样次序得到的串
叫 w 的反转
用 w^R 表示
这个字符串,它的反转得到 bbbaaababa
给了w = a1a2…an
有 n 个字符
w 的长度
是它的字符的个数，等于 n
比如说，abba 含 4 个字符
它的长度等于 4
aa 含两个字符，它的长度等于 2
a 只含一个字符，等于 1
字符串的长度
对连接运算，满足性质：
u 和 v 的连接 uv 的长度
等于 u 的长度加 v 的长度
这一点容易验证
譬如，u = aab
u 的长度是 3
v = abaab
v 的长度等于 5
这两个串的连接
u 和 v 的连接，得到这个串
它的长度
等于8
也就是 u 的长度加 v 的长度
3 加 5 等于 8
定义一个特殊的串
叫空串，用 ε 表示
有的书记成 λ
是不含任何字符的串
这个串非常特别
空串的长度等于 0
它存在
空串满足什么性质呢？
任何一个字符串 w
空串跟它左连接、跟它右连接
都不改变这个串
εw = wε = w
这个性质说明，在连接运算
空串是一个单位元
譬如，ε 跟 abba 连接
一定等于 abba
abba 跟 ε 连接，完全是一样的
这是空串
下面介绍子串
字符串的子串，是字符串中
一些部分的字符
是连续的字符
构成一个字符串
给字符串 abbab
这个串中，ab
是它的一部分
是整 abba 的子串
abba 是这个串中的一部分
它也是这个串的子串
单个 b
是子串
bbab 是子串
当然，它本身也是它自己的子串
在这子串内，有一类特殊的子串
w 表示为 uv
u 叫做 w 的前缀
v 叫做 w 的后缀
譬如，给了串 abbab
这个串的前缀有哪些呢？
空串
a、ab、abb、abba
包括它自己，都是 w 这串的前缀
这个串的后缀有哪些呢？
它自己、bbab、bab、ab、b、空串
都是这个字符串的后缀
连接运算中
如果这些串都是相同的
我们可以定义串的幂运算
譬如，有 n 个串，都是 w
它们作连接时
可以记为 w^n
(abba)^2，表示 abba 与 abba
两个相同串的连接
任何串的零次方
等于空串，这是规定
像 abba 零次方，等于空串
下面介绍字符串的“星”运算
或者叫“*”闭包
给字母表 ∑
∑* 表示
这个字母表中
所有有限的字母
或者有限的字符，构成的串的集合
叫做字母表的“*”闭包
给了字母表 {a,b}，两个字母
由这两个字母生成
所有的有限字符串
有哪些呢？
像空串、单个 a
单个 b、aa、ab、ba、bb
这些字母可以重复出现
所有构成的有限串， 这是一个无穷集合
还有一个运算，“正”闭包
给了一个字母表
它的 * 闭包
* 闭包集合刚才定义了
除去空串构成的集合
叫做这个字母表的“正”闭包
假设给了字母表 {a,b}
“*”闭包是这表示
它的“正闭”包是“*”闭包除去空串
就得到这样的集合
是一个无限集
比它的“*”闭包只少了一个空串
这节我们介绍了语言
最基本的元素--字母表
以及字母表构成的字符串
还有字符串的一些运算
这节内容介绍完毕
谢谢大家！
-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
-习题--作业
-期中考试
