计算理论01_自动机语言分解.ppt

计算理论 zhang@staff.shu.edu.cn 第 0 章 概念与语言, 第 1 章 确定自动机 第 0 章 概念与语言, 第 1 章 确定自动机 Standard Set Theory:集合论 传统，已经学过 只复习要点，ep.3-7 , cp. Conditional: A = { x | x ? N , f(x)=0 } Union: A?B Intersection: A?B Complement: Cartesian Product: A?B Power set: P (A) 或 2A (介绍记号的来源 |P (A)| = 2|A| ） Some Examples ep 6. Power set 幂集 悖论（补充） 悖论（补充） 悖论实例 补充 悖论实例 补充 悖论实例 补充 “说谎者”之所言 不是命题 而是多义句 “说谎者”之所言 不是命题 而是多义句 “说谎者”之所言 不是命题 而是多义句 理发匠定理 理发匠定理 目录悖论 目录悖论 Languages 语言，字词的集合 ep.42,cp.25 Given an alphabet ?, we can make a word or string by concatenating the letters of ?. 字母表 Concatenation of “x” and “y” is “xy” 字母的链接 Typical example: ?={0,1}, the possible words over ? are the finite bit strings. 01位串为单词 A language is a set of words. 语言，字词的集合 定义： 设? 是字母表， 则称2?的子集A为?上的语言。 More about Languages The empty string ? is the unique string with zero length. Concatenation of two langauges:  A?B = { xy | x?A and y?B } 两个语言的链接 : 字集之链 = 链字之集 Typical examples: L = { x | x is a bit string with two zeros } L = { anbn | n ? N } L = {1n | n is prime} 每个词是素数个1链成 A Word of Warning 注意 自动机的直观概念 火车车次表 自动机直观概念 Recognizing Languages 识别语言 cp22 Let L be a language ? S 自动机识别语言的直观描述（后面有形式化定义）用有限描述无限。 ： 入语言， 出判定（Y:N) a machine M recognizes L if Finite Automaton 有限自动机 ep.55,cp.34 Finite Automaton 有限自动机 ep.55,cp.34 Finite Automaton 有限自动机 ep.55,cp.34 A Simple Automaton (0) ep34, cp20, cp22 A Simple Automaton (1) cp22 A Simple Automaton (1) cp22 A Simple Automaton (2) ep34 cp22 A Simple Automaton (3) cp22 用C语言描述FA 用C语言描述FA A Simple Automaton (3) 用C语言描述 A Simple Automaton (3) 用C语言描述 Finite Automaton (def.) 有限自动机定义 cp21 A deterministic finite automaton (DFA) M is defined by a 5-tuple M=(Q,?,?,q0,F) Q: finite set of states 状态集 ?: finite alphabet 字母表 ?: transition function ?:Q???Q 转换函数 q0?Q: start state 始态 F?Q: set of accepting states 受态 A deterministic finite automaton (DFA)