分类： 学科笔记专辑

目录 第一章 基础知识1.1 集合与关系1.2 逻辑1.3 图1.4 证明技术第二章 语言及文法2.1 语言的定义与运算2.2 文法2.3 文法的分类Chomsky 文法体系分类2 型文法的表示法第三章 有限自动机和右线性文法3.1 有限自动机3.2 不确定的有限自动机（NFA）3.3 NFA 和 DFA 的等价性找出给定状态机的等效状态机的方法第一章 基础知识 1.1 集合与关系 1.2 逻辑 [ 阅读全文 ]《形式语言与自动机》学习笔记 03-29 updated

pre = ADCBFKHIGJE in = BCDKFHAGIJE pre = A DCBFKH IGJE // 找出根（第一个）和左右（按照 in 行左右两部分含有的字母） in = BCDKFH A GIJE A DCBFKH IGJE // 得到大致结构 // 后面对左右递归如此操作 for DCBFKH BCDKFH D CB FKH BC D KFH D CB KFH for CB B[ 阅读全文 ]数据结构：前序+中序序列确定树

呜呜呜呜呜我凉了。 北邮的同学们，卷起来吧。加速！ 关系 关系的性质 如何求关系的补、并、交、逆 解释自反、对称、反对称、连通、传递、等价等的概念 等价关系：如何证明关系等价 偏序关系：如何证明偏序关系 求传递闭包：求传递闭包的 Warshall 算法详解 关系的同构：如何证明关系同构 格 如何画哈赛图：根据关系的描述画出哈斯图 从哈塞图判断是不是格 群论 同态：如何证明同态？ 同构：如何证明群/[ 阅读全文 ]离散数学（下）期末重点再梳理

生成函数：一种形式幂级数，其每一项可以提供关于这个序列的信息。 普通生成函数 $\sum_{n=0}^{\infty}a_nx^n$ 简单序列的生成函数 $1, 1, \cdots$ 常数列： $$ \sum_{n=0}^{\infty} x^{n}=\frac{1}{1-x} $$ $1, a, a^2, a^3, \cdots$ 序列 $$ \sum_{n=0}^{\infty}(a x)^{[ 阅读全文 ]离散数学：利用生成函数求解递推关系

div 和 mod 记号 用法： $ 2 = 8 \operatorname{div} 4 = 9 \operatorname{div} 4$ 除法向下取整 $ 0 = 8 \operatorname{mod} 4; 1 = 9 \operatorname{mod} 4 $ 除法余数 $ \equiv $ 记号 $ 17 \equiv 5 (\operatorname{mod} 6) $ 因为 1[ 阅读全文 ]离散数学笔记（数论部分）

过程详情 【例子】关系的矩阵是： $$ \boldsymbol{W}_{0}=\left[\begin{array}{llll} 0 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{array}\right] $$ 求传递闭包。 【分析与解答】 我们看第 1 列：$\pmatrix{0\\1\\1\\0}$。 [ 阅读全文 ]求传递闭包的 Warshall 算法详解