• 有穷自动机，下推自动机，图灵自动机
• 推荐书籍：《自动机理论、语言和计算导论》、《自动机理论、语言和计算导论》
• 课件下载：

导论

• 自动机理论历史

• 主要学习内容：有穷自动机、下推自动机、图灵机
• 有穷自动机 ： 1、具有有限内存的设备可以做什么 以及不能做什么 2、引入仿真：一台设备“模仿”另一台设备的 能力 3、引入不确定性：设备做出任意选择的能力
  下推自动机：1、这些设备与语法有关，它们描述了编程（和自然）语言的结构
• 形式语言：语言是有限长度的句子的集合，1、所有句子均由有限的符号构成的符号串 2、所有符号都来自于一个有限的字母表 3、语法是枚举语言中所有句子的装置 4、如果一个句子属于该语言，则一定可以枚举出来 5、如果枚举出一个句子，则一定属于该语言

课程大纲

• 有穷自动机和正则语言
  有穷自动机 Deterministic finite automata (DFA)
  非确定有穷自动机 Nondeterministic finite automata (NFA)
  正则语言 Regular languages
  正则表达式 Regular expressions (RE)
  正则语言的判定性质 Decision properties
  正则语言的闭包性质 Closure properties
  有穷自动机的构造、转换、最小化等算法
  等价性证明
  正则语言各种性质的证明

• 下推自动机和上下文无关语言
  上下文无关语言 Context-free languages (CFL)
  上下文无关文法 Context-free grammars (CFG)
  下推自动机 Pushdown automata (PDA)
  判定和闭包性质 Decision and closure properties
  相关算法和证明
  在编程语言中的应用

• 图灵机和递归可枚举语言
  递归语言和递归可枚举语言 Recursive and recursively enumerable languages
  图灵机 Turing machines (TM)
  问题的可判定性 Decidability of problems
  可计算的边界和限制

• 不易处理的问题 Intractable problems
  不能在多项式时间内解决的问题
  NP完全和NP难（选讲）
• JFLAP软件的使用
  支持  非确定有穷自动机  非确定下推自动机  多带图灵机  数种类型的文法，  解析和L系统。

• 语言到DFA，举例构造{0,1}上DFA接受所有已101结尾的符号串
  解法1：构建所有状态，选取指定的状态作为终态

有穷自动机引论

• 什么·是FA？

确定型有穷自动机-Deterministic Finite Automata

• 一个确定型有穷自动机，可形式化定义为一个五元组{Q, ∑ , δ, q0, F }，包含：
• 1、状态：A finite set of states (Q, typically)
  2、字母表：An input alphabet(Σ, typically)
  3、转移函数：A transition function(δ, typically)
  4、初始状态：A start state(q0, in Q, typically)
  5、终结状态：A set of final states(F ⊆ Q, typically).
  （此时，Final等同于Accept）

• 图示例：

• 转移表：

• DFA的语言：1、有种类的自动机都定义了语言 2、如果A是自动机，则L(A)是它的语言 3、对于DFA A，L(A)是从起始状态到终结状态的路径上标记符号串的集合。 4、形式化: L(A) = 满足δ(q0, w)属于F的符号串w 的集合
  

正则语言

• 一个语言L能被DFA接受，则称他是正则的（此DFA无法识别非L中字符，且正则无法识别无穷数列）
• 证明题：证明一个语言非正则

NFA

• 从一个状态出发可以进入多个状态（遍历所有可能）