"HIT 形式语言与自动机 2023年期末复习笔记"

HIT 形式语言与自动机 期末复习笔记（2023） 本文是作者在2023年春季学期期末考试前的复习笔记，目的是整理大部分考点和知识理解，以及一些自己做的题目和做题过程中的总结。笔记中给出了一些题目的详细分析和解答过程，希望能给HITer一些复习参考价值！ 第一章 课程简介与基础知识 1.1 定义类 本节介绍了字符串的定义。字符串是由某字母表中符号组成的有序序列。此外，还介绍了空集和幂集的定义。根据集合的幂的定义，空集的幂集强制定义为只含有空字符串的集合。 本节还介绍了一些形式化证明方法，包括演绎法、归纳法和反证法。 1.2 题目 本节给出了两道题目，分别是关于字母表克林闭包的性质。第一道题中指出了字母表克林闭包中一定有无穷多个元素，而集合的克林闭包不一定有无穷多个元素。举例说明了空集的克林闭包为只含有空字符串的集合。 第二道题讨论了任意字母表克林闭包中的字符串长度，指出了字符串的长度可以任意长，但没有无穷长的字符串。 第二章 有穷自动机 2.1 DFA（确定的有穷自动机） 本章介绍了确定的有穷自动机（DFA）的定义。一个DFA包含有穷状态集、有穷输入符号集（或字母表）、状态转移函数、初始状态和终结状态集（或接受状态集）五个要素。 状态转移函数定义了从一个状态经过一个输入符号转移到另一个状态的规则。 本章还介绍了扩展转移函数，将状态转移函数扩展到字符串的转移过程中。扩展转移函数的定义为从一个状态通过一个字符串转移到另一个状态的规则。 以上是本章的主要内容。 总结起来，本文是作者整理的形式语言与自动机课程的期末复习笔记，包含了课程的基础知识和重要考点。笔记详细介绍了字符串的定义、空集和幂集的性质，以及形式化证明方法。另外，笔记还给出了两道题目，讨论了字母表克林闭包的性质。章节中还介绍了确定的有穷自动机（DFA）的定义，包括状态集、输入符号集、状态转移函数、初始状态和终结状态集等要素，并介绍了扩展转移函数的概念。希望这些复习笔记对HITer的复习有所帮助！