目录

一，自然语言

1，自然语言的范畴

2，最小单元

（1）音节、读音

（2）单字、单词

（3）语素

（4）词

3，语法、词法、句法

（1）抽象性

（2）生成性

（3）系统性

（4）层次性

（5）递归性

4，语义

二，形式语言

1，形式语言

2，最小单位——Token

3，形式文法的组成

（1）VT

（2）VN

（3）S

（4）P

4，形式文法的简写

5，四种文法

（1）0型文法

（2）1型文法

（3）2型文法

（4）3型文法

（5）四种文法的关系

---

一，自然语言

1，自然语言的范畴

自然语言的范畴，主要包括读音、字形、含义三大类。

读音是耳朵相关，字形是眼睛相关，含义是大脑相关，这三者都互相相关，并不独立。

读音方面，主要是音节和音调。

字形方面，主要是字母或者偏旁部首怎么组成单词。

含义方面，主要是包括语法、语义。

2，最小单元

简单的理解，英语最小单元是字母，大一点是词，再大一点是词组，再大一点是句子，汉语最小单元是字，大一点是词，再大一点是词组，再大一点是句子。

看起来还挺统一的，但从字形上，汉字还可以拆分，从发音上，一个汉字是一个独立的发声单元，而英语中字母却不是独立的发声单元，从含义上，单英文字母是没有含义的，汉字是有含义的，很多英语单词可以和汉字的含义对应，比如good好，look看。

（1）音节、读音

音节（Syllable）是语言中单个元音音素和辅音音素组合发音的最小语音单位，单个元音音素也可自成音节。
汉语的音节是由声母和韵母相拼组成的语音单位，单个韵母也可自成音节。
对英语西语俄语等非声调语言来说，其发音主体是音节。对汉语、泰语等声调语言来说，其语音除了音节还有声调，音节加上声调就是读音。

（2）单字、单词

汉语的单词即汉字，一个汉字就是一个音节，汉字的字形由偏旁部首构成。

英语的单词就是单词，有单音节单词，也有多音节单词，单词由英文字母构成。

（3）语素

语素是指语言中最小的音义结合体。

对于单音节语，如汉语、越南语、泰语等，语素大部分都是单音节的。

对于其他语言，语素由一到多个音节组成。

• 汉语的单音节语素：天、地、人、跑、跳、唱、红、白
• 汉语的双音节语素：琵琶、乒乓、澎湃，其中单个的字没有含义
• 汉语的多音节语素：喜马拉雅、珠穆朗玛，其中的马作为单个的字倒是有含义，但是并没有组成喜马拉雅这个词的含义。

（4）词

词是构成句子的最小单位。

语素和词的含义很接近，词是一到多个语素组合而成。

比如，“春来了吗？”，春是语素，也是词。“春天来了吗？”春是语素，天是语素，春天是词。

3，语法、词法、句法

语法是从众多的语法单位里抽象出其中共同的组合方式、类型及如何表达语义的规则。

语法包括词法和句法。语法也叫文法。

词法，就是词的分类、性质、作用。词法也叫字法。

句法是词如何构成句子，即句子的分类和构成规则等。

语法有如下主要特点：

（1）抽象性

语法从词和句的个别和具体的东西中抽象出来，把作为词的变化和用词造句的基础一般的东西拿来，并且以此构成语法规则、语法规律。

例如汉语里有“看看、说说、写写、学习学习、讨论讨论”这一词的重叠现象，这反映出一条词的变化规律：有些动词可以用重叠的方法来表示动作的某一语义类型，即表示少量或短时。

语法学的任务是描写，解释组成词、短语和句子的规则和格式。由此可见，语法具有抽象性、概括性。

（2）生成性

我们可以根据有限的语法规则造出无数合格的句子来，这就表现了语法的生成性。语法规则的生成性，集中的表现在两个方面：组合关系和聚合关系。

组合关系指的是语序结构。比如我吃饭（S+V+O）。你看书。他写字。上述都是同一种组合关系。
聚合关系，你、我、他都是人称代词，是一种聚合关系。饭、书、字在上述例子中都做宾语（实体名词），也是一种聚合关系。

（3）系统性

语法是一个严密的立体的开放的系统网络。

所谓“严密”，是指系统的内部是相互制约的，要受到一定的规则的支配，不是可以随心所欲的。

所谓“立体”，是指语法系统包括了句法结构，语法意义，语言运用这三个交叉的不同平面。

所谓“开放”，是指语法系统是发展变化的，一直在不断地自我完善，旧的成份被逐渐淘汰，新的因素在不断产生。

语法系统内部又由若干个子系统构成，例如语素系统，词类系统，短语系统，句子系统，句群系统，每个子系统可能由若干个孙系统构成。词类系统内部可以分为实词系统和虚词系统。句子系统内部可以分为单句系统，复句系统等等，从而形成一个系统网络。

（4）层次性

语法从表面上看是线性排列的东西，但是语法结构却是有层次性的。

语法的层次性与语法的递归性密切相关。

（5）递归性

递归是说，各种语法结构的关系是有限的，但是在语言单位的组合过程中，可以反复无限地使用这些有限的规则，从而使句法结构复杂化。例如：我买书。/我买一本书。/我买一本有趣的书。

4，语义

关于知识的概念没有明确的定义，一般来说，知识为人类提供了一种能够理解的模式用来判断事物到底表示什么或者事情将会如何发展。从知识的陈述特性上来看，知识即指用来描述信息的概念、概念之间的关系，以及概念在陈述具体事实时所必须遵守的条件。从这一点看，对于信息的语义以及信息语义之间的关联关系的描述本身就是一种知识的表达，因此在许多研究中，往往将语义的描述等同于知识的描述。

二，形式语言

1，形式语言

为了消除自然语言的多义性，我们发明并使用形式语言。形式语言是只注重形式而不注重内容，即只有语法而没有语义。

形式语言是一个字母表上的某些有限长字符串的集合。

数学家用的数字和运算符号、化学家用的分子式、程序员用的编程语言都是形式语言。

形式语言理论，只研究语言的语法而不致力于它的语义。

形式语言的语法，同样分为词法和句法。

2，最小单位——Token

形式语言的最小单位是Token

Token的概念相当于自然语言中的单词和标点、数学式中的数和运算符、化学分子式中的元素名和数字。

关于Token的规则就是词法，Token如何形成形式语法就是句法。

以编程语言为例：

int func();

int、func、(、)、; 共5个token

3，形式文法的组成

文法即语法，形式文法就是形式语言的语法。形式文法包括词法和句法。

一个形式文法G由四个部分组成,可记作G={VT, VN, S , P }

（1）VT

VT是终结符(terminal)构成的集合，终结符就是Token

（2）VN

VN是非终结符(nonterminal)构成的集合，非终结符是Token组合而成的，比如短语，句子。

VT和VN的交集是空集，并集是文法符号集。

符号串是由文法符号集的若干成员依次排列形成。

（3）S

S是开始符号(start symbol)，是语法中最大的语法成分（相当于自然语言中的句子）

（4）P

P是生成式(production)构成的集合，描述怎么通过一个符号串得到另外一个符号串。

生成式的一般表示法：   a -> b，读作“a定义为b”

例如，包含加法和乘法的表达式，可以表示成：

其中，id是标识符，E是表达式

生成式有四条，分别表达了：

• 表达式+表达式 是 表达式
• 表达式*表达式 是 表达式
• （表达式）是 表达式
• 标识符 是 表达式

4，形式文法的简写

在不引起歧义的情况下，只用生成式就可以用来表示整个文法。

生成式的简写：

（1）候选式合并

a->b1  a->b2  a->b3

可以合并简写成

a>b1 | b2 | b3

所以上面的文法可以简写成 E -> E+E | E*E | (E) | id

5，四种文法

（1）0型文法

0型文法也称短语文法、短语结构文法、无限制文法。

一般表示法：a -> b，其中符号串a至少需要包含1个非终结符。

能力相当于图灵机，或者说任何0型语言都是递归可枚举的。

（2）1型文法

1型文法也称上下文有关文法，其能力相当于线性界限自动机。

一般表示法：a1a2a3 -> a1ba3，其中符号串a2的长度不超过符号串b的长度

即a2定义为b是有上下文的限制的。

（3）2型文法

2型文法也称上下文无关文法，其能力相当于非确定的下推自动机。

一般表示法：A->b，其中A是某个非终结符。

例如，表示标识符的上下文无关文法：

（4）3型文法

3型文法由于等价于正规式，所以也称正规文法、正则文法

正则文法分为左线性文法、右线性文法。

左线性文法的一般表示法：A->Bw，或A->B，其中w是终结符号串

右线性文法的一般表示法：A->wB，或A->B

所以，正则文法的符号串最多只能包含1个非终结符，而且只能全部在最左边，或者全部在最右边。

例如，表示标识符的右线性文法：

 不难发现，这个文法和上一节的表示标识符的上下文无关文法是等价的。

（5）四种文法的关系

0型文法包含1型文法，1型文法包含2型文法，2型文法包含3型文法。

一、前言

本文总结北邮计算机学院《形式语言与自动机》的学习资料，希望能帮到学弟学妹，打好基础。

从名字也能知道，这门课就是学形式化语言及其对应的自动机。这门课相对简单，知识脉络十分清晰。总结一下就是很简单。

《形式语言与自动机》同《离散数学》的感觉其实比较像，不难，也不会花太多时间，学科结构清晰。

二、思维导图

以下是自己总结的 XMind 思维导图，可以帮助梳理知识脉络，需要自取
链接：https://pan.baidu.com/s/1h7TI9tWXqFKibtPS8urVdA
提取码：6ld7

放张图：

三、课后题

这门课在网上的资源较少，少有学校开这门课，因此课后题显得尤为重要，考试基本就是你没做过的课后题原题及其变种。

因为教材使用的是北邮自己编的教材，没有制作标准答案，只有一些网上流传的答案，不过质量还可以，除了有点丑以外，答案基本正确，不过因为版本原因，出现很多缺题现象。这里提供自己总结的课后题答案：

形式语言与自动机 第二章 课后题答案
形式语言与自动机 第三章 课后题答案
形式语言与自动机 第四章 课后题答案
形式语言与自动机 第五章 课后题答案

四、其他学习资料

其他学习资料有限，我自己找到最好的是机械工业出版社的《形式语言与自动机导论》，作者是 Peter Linz，直接去看中文版就好。里面的例题和课后题比课程要求的要高一些，不过可以拓宽思路，考试万一遇到新颖的题目不至于脑子一片空白。

期末时候可以把期中题做一下用来复习前 2 章。

五、关于考试

因为疫情，我们只有期末考试，期中考试不了解，不过期中测试题还是有点难度的。期末考试难度较低，拿高分很简单，但要注意细节（比如起始状态能不能直接到 F）。

考试主要内容为设计自动机、文法等，这门课的考查点都很简单。要说有难度的就是设计题，但是如果设计不出来文法，也可以直接设计自动机然后转文法，还有就是 CH4 的泵浦引理（CH3 的泵浦引理出题很简单），可以多看看课后题和《形式语言与自动机导论》的泵浦引理，记住一些常见的证明思路。

以上，祝大家取得满意的成绩！

哈尔滨工业大学2019年《形式语言与自动机》期末试题

1. Design a DFA for the language L = {w∈{0,1}* | w contains both 01 and 10 as substrings}.

2. Design a NFA within four states for the language {a}*∪{ab}*.

3. Design regular expressions for language over Σ = {0,1}.
   (1).All strings contain the substring 001.
   (2).All strings expect the string 001.

4. Prove that L = {0^m1ⁿ | m/n is an integer} is not regular with pumping lemma.

5. Convert the following NFA into DFA with subset construction.
   

6. Give a context-free grammar for L = { aⁱb^jc^i+j|i,j>=0}

7. Let L be the language generated by the grammar G below
   S->AB|BBB
   A->Bb|ε
   B->aB|A
   (1).消除空产生式
   (2).消除单元产生式
   (3).转换到CNF

8. Design a PDA for L = {w∈{a,b}*|w has more a’s than b’s}

9. Prove : for every context free language L, the language L’ = {0^|w||w∈L} is also context free.

10. Design a Turing Machine that computes the following function f:0ⁿ->Binary(n)
    Where integer n>=1 and binary(n) is the binary representation of n.
    For example: f(0³) = 11 f(0⁵) = 101.

注：此题目为考试试卷实录，敬请放心食用。