形式语言与自动机

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

ppt01下载

ppt02下载

目录

• 导论
  • 课程大纲
• 有穷自动机引论
  • 确定型有穷自动机-Deterministic Finite Automata
  • 正则语言
  • NFA

导论

• 自动机理论历史

• 主要学习内容：有穷自动机、下推自动机、图灵机
• 有穷自动机 ： 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

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