当前课程知识点：软件理论基础 > 第五章 正则文法和正则语言 > 5.2 线性文法 > Video
欢迎同学们来到《软件理论基础》的MOOC课堂
现在讲述第五章 第二节 线性文法
在上一节里面
我们给出了文法的定义
文法它是个四元组
四元组里面最重要的就是产生式
产生式它的左边是一个变量
右边是一个句型
它就有若干个变量和若干个终结符
就是在右边的字符串里面
或者它的句型里面
最多只有一个变量
那对这样的文法我们把它叫做线性文法
那下面我们看这类文法
也就是我们前面多次出现过S产生aSb
S产生ε
这个文法里面
右边你看这里
这一个变量
这里一个变量
所以这个文法就是一个线性文法
我们再看另外一个例子
这个文法也是它的右边这里有一个变量
这里右边也只有一个变量
这里右边没一个变量
所以这也是一个线性文法
我们再看一个例子
这个文法有四个产生式
这四个产生式里面它的右边
也这个只有一个变量
这是只有一个变量
这里只有一个变量
这里没变量
所以这也是一个线性文法
这个线性文法实际上
我们把它推导 可以把它的句子写出来
它的语言实际上就是我们熟悉的
a的n次方 b的n次方
这个跟我们前面讲的
那个文法产生的语言是一样的
也就是说这个语言
可以通过不同的文法来产生它的
这个线性文法它表示的这语言
我们之前已经出现过
下面我们看什么是非线性文法
我们看这个文法
第一个产生式
它的右边有两个变量
尽管其它的产生式
它 你看这里只有一个 这里只有一个
但是它有一个产生式
是两个或者多于两个的这个变量
那这个文法就是非线性的
像这个文法它产生的语言
这个语言
这是以后 我们也多次碰到的
这个语言表示什么呢
你像na（w）
实际上它就表示这个串w当中a的个数
那nb（w）表示这个串当中b的个数
也就是这个串当中a的个数
跟b的个数是相等的
把这个串放在这个语言里面
在刚才讲的线性文法里面
那还有一种比线性文法
更特殊的一种文法
像右线性文法
因为我们讲的线性文法
它的产生式 最右边最多只有一个变量
那如果说我们讲了最右边
它的变量如果有的话
只是这种形式
也就是说这种文法只有两类产生式
一种是a产生xB
x是终结符串
b是一个变量
或者是a产生x
这个x这里面都是终结符串
那这一看的话 大家可以看出
这个里面 肯定是一个线性文法
因为它要么这里没有变量
如果有变量的话
它这种只有一个
而且这个变量
是位于这个字符串里面最右边
所以我们把这样的文法叫做右线性文法
下面我们看一个例子
这里S产生abS
这个变量
在这个字符串里面位于最右边
S产生a这里没有变量
所以这就是我们一个右线性文法
还有一种文法
也是线性文法
这个文法它是所有产生式当中
也就是a产生bx
或者是a产生x
x是终结符的串
这也是线性文法
它这里面如果有变量
这个产生式里面
这个变量是位于这个字符串当中最左边
下面我们看一个例子
这里给出了这里四个产生式
它这里面前三个产生式里面
它的右边的字符串都含一个变量
而且这个变量你看
都位于这个串的最左边
所以这也是一个线性文法
而且它是左线性文法
右线性文法 或者是左线性文法
叫做正则文法
实际上正则文法就是右线性文法
或者是左线性文法
我们看这个例子
我们刚才给的这个文法
这个文法里面
它就是一个右线性文法
我们再看这个例子
这个文法是一个左线性文法
这两个文法大家可以验证
它们的描述语言都是相同的
就是这个语言
实际上大家很熟悉
这里是一个正则表示的语言
实际上就是正则语言
也就是说正则文法它描述的语言
跟正则语言它们之间有一定关系
这是我们在下一节当中我们要介绍的
好 这一节讲到此
谢谢大家
-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
-习题--作业
-期中考试
