内容截取自《形式语言与自动机+哈工大》https://www.bilibili.com/video/BV1oE4116794?p=2&vd_source=d450eb5d34aab044271ddba341b2d398
老师你是陈泽吗↓
Week01
1. 字母表
2. 字符串
3. 空串
4. 字符串的长度
5. 字符串连接
6. 字符串的幂
7. 集合的连接
8. 集合A的幂
9. 克林闭包(Kleene Closure)
10. 正闭包(Positive Closure)
Week02
1. DFA Definition
A deterministic finite automaton (DFA) A = (Q, Σ*, δ, q0, F*) is given by:
- A finite set of states Q （有穷状态集）
- A finite set of input symbols, the alphabet, Σ （有穷输入符号集或字母表）
- A transition function δ ∈ Q × Σ → Q （状态转移函数）
- An initial state q0 ∈ Q （初始状态）
- A set of final states F ⊆ Q （终结状态集或接受状态集）
The initial states are sometimes called start states, and the final states are
sometimes called accepting states.
As an example consider the following automaton
D = ({q0, q1, q2}, {0, 1}, δD, q0, {q2})
transition table
transition diagram
笛卡尔积得到的两个transition diagram合并的图
扩展转移函数
↑两个公式等价
The language of a DFA （DFA语言与正则语言）
NFA
Week03 正则表达式
语言运算回顾
四则运算表达式递归定义
运算符的优先级
构造正则表达式
正则表达式的带书定律
并运算∪
连接运算
闭包运算
判断两个正则表达式是否相等
Week05 泵引理
正则语言泵引理
正则语言的封闭性
封闭性定义
反转定义
正则语言判定性质
DFA最小化
Week07 (PDA)
Week08 (Turing Machine)
图灵机的形式定义
例题
瞬时描述
转移符号
图灵机语言
整数函数计算器
