形式语言与自动机

ppt01下载

ppt02下载

主要学习内容：有穷自动机、下推自动机、图灵机
有穷自动机： 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：构建所有状态，选取指定的状态作为终态

一个确定型有穷自动机，可形式化定义为一个五元组{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 的集合

0 人点赞