形式语言与自动机理论复习笔记（更新ing）

时间： 2023-12-21 admin IT培训

形式语言与自动机理论复习笔记（更新ing）推荐度：
相关推荐

一定记住画FA需要写S->和终止状态是双层圈

第一章绪论

1.1集合的基础知识

无穷集分为可数集（奇偶数集/整数集/非负奇偶数集/有理数集）与不可数集（实数集），判断依据是是否以自然数（0,1，2,3...）为基数

对称差：

A⊕B=(A∪B)-(A∩B)=(A-B)∪(B-A)。（图中蓝色部分）

笛卡尔积：

！！！！！！

幂集：

!!!!!!

1.2关系

自反对称传递：

？？？？？？

正闭包：

具有传递性

克林闭包：

R *具有自反性、传递性。

R * = R 0∪R +

！！！！！！

1.3图（无笔记）

1.4语言

字母表：

是一个非空有穷集合，字母表中的元素称为该字母表的一个字母，又叫做符号或者字符

字母表具有非空性和有穷性。

字母表的字母：

具有两个特点，整体性/不可分性（aa/aaa也属于字符）+可辨认性/可区分性（字母表中的字符两两互不相同）

{a，a′，b，b′}、{aa，ab，bb}是字母表

空串: 记为ε, 有0 个字符的串. –

字母表Σ可以是任意的, 但都满足ε ∉ Σ

字母表的乘积：

字母表∑的n次幂 ∑0={ε}

字母表的克林/正闭包：

克林闭包比正闭包多一个空串

∑*={x|x是∑中的若干个，包括0个字符，连接而成的一个字符串}。

任取x∈∑* ，x叫做∑上的一个句子。

∑+={x|x是∑中的至少一个字符连接而成的字符串}。

x，y∈∑* ，a∈∑，句子xay中的a叫做a在该句子中的一个出现。

当x=ε时，a的这个出现为字符串xay的首字符，当y=ε时，a的这个出现是字符串xay的尾字符

任取x∈∑* ，句子x中字符出现的总个数叫做该句子的长度，记作|x|。 – 长度为0的字符串叫空句子，记作ε。

|abaabb|=6 |bbaa|=4 |ε|=0 |{ε}|=1，而|Φ|=0。

字符串的连接：

前缀与后缀

真前缀:后面非空

用x T表示x的倒序

语言：

任取L（集合）属于∑* ，L称为字母表∑上的一个语言(language)，任取x（元素）∈L，x叫做L的一个句子。

习题类型（重点）

第二章文法

2.1启示

2.2形式定义

非终极符（变量）与终极符交集为空集，开始符号是非终极符的元素

产生式的左侧是正闭包，右侧是克林闭包

用|表示拥有相同的产生式左端，右侧所有终极符称为候选式

判断四元组是否满足文法要求：

不符合：产生式中，S与D、e、F不在v与t的正闭包内，且开始符S不是非终极符

推导、派生与归约

用产生式的右部替换产生式的左部

归约是推导的逆过程。

语法范畴

句子与句型：

句子是全部都是终极符

句型可能包括非终极符

句子一定是句型，但是句型不一定是句子

句型的推导

在需要替换的产生式左右标下划线

2.3文法的构造

文法写作g，一种语言可以由不同文法构成

文法的第一个产生式左侧是开始符

构造文法：

？？？？？？？？？？？

2.4文法的乔姆斯基体系

乔姆斯基体系根据产生式的形式，将文法分为四种：

0型文法/短语结构文法（phrase structure grammar，PSG）

正常满足G=（V,T,P,S）的都是短语结构文法

1型文法/上下文有关文法（context sensitive grammar，CSG）

产生式右侧长度>=左侧

2型文法/上下文无关文法（context free grammar，CFG）

产生式右侧长度>=左侧并且左侧只有一个非终极符

3型文法/正则文法/正规文法（regular grammar，RG）

（单个非终极符->终极符的正闭包

单个非终极符->终极符的正闭包+单个非终极符）

如：G1：S->0|0S是正则文法:

G2:S->0|1|0A|1B,A->0,B->1是正则文法

为什么这个是正则文法，明明没有看到非终极符

文法的分类：

？？？？？？？？？？

文法和语言符合相同规则

线性文法：

这里与正则语言不同的是，wx都是终极符的克林闭包，而非正闭包

右线性（RG）：S->0|0S

左线性：S->0|S0

线性：S->0|0S0

线性文法/语言不一定是左右中的任何一种，？？？？？左/右线性也不一定是线性语言（这里强调的是一定，not all）

左线性文法与右线性文法等价

右线性：

左线性：

推导，推出123456这个字符串

归约，从123456推出最初的开始符S

左线性文法的产生式与右线性文法的产生式混用所得到的文法不是RG。

2.5空语句

即只有可能在短语结构文法/语言中出现空产生式/语句

在RG、CFG、CSG中，都不能含有空产生式。所以，任何CSL中都不含有空语句ε。从而 CFL和RL中都不能含空语句ε。

空语句ε不影响该语言的有穷性

除了为生成空语句ε外，空产生式可以不被用于语言中其他任何句子的推导中

如果S不出现在G的任何产生式的右部，则增加空产生式的文法类型不改变，仍是csg/cfg/rg

增加空句的语言类型不改变

前者是一个最终结果，后者是语言

第二章课后习题

第二题：构造符合要求的文法？？？

RG是正则文法，格式为：S->0|0S与G2:S->0|1|0A|1B,A->0,B->1，即wB与B同时出现在右侧

CSG是上下文有关文法，要求是每一个产生式右侧长度>=左侧

CFG是上下文无关文法，要求是每一个产生式右侧长度>=左侧并且左边只有一个非终极符

关于范围：RG<CFG<CSG<短语结构

第三题：给出句子的推导和归约

推导是沿着产生式往后推，归约是从结果往产生式推

第六题：给出G的每个语法范畴所代表的集合？？？？？

第七题：描述文法定义的语言？？？？？？

第八题：给出字母表上的语言的文法(而非串）？？？？？

第九题：给出语言的文法？？？？（是包含vtps的四元组格式）

第三章（重点，占比30%）

例题3-2

注意此处终止状态下输入0/1都是回到终态；终态是双层圈；使用S->标出开始状态；每个状态q都有自己的顶点

先写出移动函数表再画状态转移图

例题3-3

此图易错：q0输入1也要回归q0；q3输入1回归q1；q3输入0回归q3，因题目意思是至少三个连续0

此题易错：q3输入1去q0因为达成了001，q1输入1重新开始去q0

例题3-4

语言{0n1n|n>=1}(n次方）为无穷种可能，无法构造出有穷自动机，此种01都是n次方，次方数相同

？？例3-5

？？例3-6

？？？？？？？？？

大题1：3.3.2例3-7：NFA对应的DFA的状态转移函数

此表中√指从开始状态可达的，可达可以通过多步实现，不一定是直接可达

只有可以达到的状态集合才会被画出来，其他都是无效的

以及只要含有终止状态，就写入终止状态的中，故有五个终止状态

？？？？？

从状态转移图写出等价的正则文法，当产生式右侧是终止状态时，额外写入终止状态前读入的字符

例题3-10

从产生式画FA需要额外引入终止状态E,将常数与E连接

左线性文法等价暂时不考

第三章课后习题

？？第一题：给出DFA的形式描述

？？第二题：构造语言的DFA（给出形式描述或者画出状态转移图

同时输入两个字符，用0,1这种表示，而非0/1

形式语言与自动机理论-蒋宗礼-第三章参考答案(最新整理） - 豆丁网 (docin)

形式语言与自动机理论 复习笔记（更新ing）