1. 理解形式语言学
形式语言通常作为定义编程语言和语法的基础，是正式版本的自然语言的子集。它能被具有有限计算能力的机器所解析。
1. 语言形式与语言功能:形式语言学研究语言的结构形式,而不关注语言表达的具体功能或意义。它把语言视为一套规则来递归生成句子,这些规则构成语言的「语法」。
2. 符号系统:形式语言学使用抽象的符号系统来研究语言结构,而不使用具体的语音或词汇形式。常用的符号系统有布尔代数、形式逻辑等。
3. 递归规则:语言的结构是通过一组递归规则构建的,即较小的结构重复应用到更大的结构上。这些规则定义了语法,其自顶向下的应用可以生成所有的合法句子。
4. 上下文无关文法:形式语言学通常采用上下文无关文法来描述语言结构,即一个符号的产生仅依赖于该符号左部的符号,而与上下文无关。这种文法简洁且易于描述。
5. 语言等价性:可以通过等价性测试判断两种语言的表达能力是否相同。常用的等价性测试有越似变换、万能文法等。
6. 启发式算法:形式语言学还研究语言结构的学习问题,常使用启发式算法来学习文法,如句法分析算法等。
2. 理解自动机
自动机是有限状态机(FSM)的数学模型。自动机是一种抽象的计算模型,用于识别和生成形式语言中的字符串
1. 状态:自动机中的状态表示识别或生成过程中的中间结果。初始状态表示开始,终止状态表示结束。
2. 字母表:自动机运算所使用的符号集合,它定义了自动机可以识别或生成的字符范围。
3. 转移函数:定义了从一个状态到下一个状态的转移规则。当输入一个字母表中的字符时,会根据转移函数转到新的状态。
4. 确定性vs非确定性:确定性自动机的转移是唯一的,而非确定性自动机可以有多个转移选择。后者更加灵活但解析难度较大。
5. 有限自动机:具有有限个状态和字母表的自动机。这是一种比较简单但功能也较弱的模型。
6. ε-转移:自动机可以在不消耗任何输入的情况下从一个状态转移到另一个状态,这种转移成为ε-转移。它增加了自动机的表达能力。
7. 接受与拒绝:对输入字符串,如果自动机可以从初始状态转移到某终止状态,则该字符串被「接受」;否则被「拒绝」。
8. 正则表达式:一种简洁的语法,可以描述某个语言中所有合法字符串的集合。许多语言的规则可以用正则表达式表达。
a) 为什么研究自动机理论
确定的有穷自动机 DFA
不确定的有穷自动机 NFA
带空移动的有穷状态机 ε-NFA
正则语言的识别器 FA finite automation 有穷状态自动机
δ——状态转移函数(transition function)，有时候又叫做状态转换函数或者移动函数。δ：Q×Σ->Q，对所有(q，a)∈Q×Σ，δ(q，a)=p表示：M在状态q读入字符a，将状态变成p，并将读头向右移动一个带方格而指向输入字符串的下一个字。
系统或部件是处在有穷多个“状态”之一。
状态的目的是记住系统历史的有关部分。
好处：用固定的资源就能实现系统
3. 乔姆斯基体系
由语言学家诺姆·乔姆斯基提出的文法类型体系,它按照文法规则的约束程度将文法划分为4种类型:
1. 无类型文法(Type 0):可以包含任意类型的规则,无任何约束,生成能力最强但难以处理。 PSG
2. 上下文有关文法(Type 1):允许出现在左部但不在右部的非终结符,增加了一定约束,生成能力减弱但仍较强。 CSG
3. 上下文无关文法(Type 2):每个产生式的左部和右部出现的非终结符必须相同,此类文法简洁,容易处理且生成能力适中。 CFG
4. 正则文法(Type 3):产生式仅允许在右部增加终结符,是所有文法类型中最简单且生成能力最弱的。RL
a) G=(V， T，P，S）
V: 变量非空有穷集 T: 终极符 S：开始符号 P:产生式
推导与归约和产生式不一样。 推导与归约是一一对应的
约定：对一个文法，有一个字母表Σ，使得只列出该文法的所有产生式，有一个字母表Σ，使得且所列第一个产生式的
左部是该文法的开始符号。
定理：
1. L是一个左线性语言的充要条件是存在文法G，G中的产生式要么是形如：A->a的产生式，要么是形如A->Ba的产生式，使得L(G)=L。其中A、B为语法变
量，a 为终极符号。
2. 左线性文法的产生式与右线性文法的产生式混用所得到的文法不是RG.
3. 设G=(V，T，P，S)为一文法，则存在与G同类型的文法G′=(V′，T，P′，S′)，使得L(G)=L(G′)，但G′的开始符号S′不出现在G′的任何产生式的右部。
4. L(G’)包含于L(G)
5. 往L中添加空串
⑴ 如果L是CSL，则L∪{ε}仍然是CSL。
⑵ 如果L是CFL，则L∪{ε}仍然是CFL。
⑶ 如果L是RL，则L∪{ε}仍然是RL