07879离散数学-屈婉玲(形式语言与自动机)111.ppt

形式语言和 自动机初步 11.1 形式语言与形式文法 字符串和形式语言 形式文法 形式文法的分类 0型文法 1型文法 或上下文有关文法 2型文法 或上下文无关文法 3型文法 或正则文法 * * 第11章 形式语言和自动机初步 11.1 形式语言和形式文法 11.2 有穷自动机 11.3 有穷自动机和正则文法的等价性 11.4 图灵机 语言的基本要素 汉语 字符:汉字和标点符号 字符集:合法字符的全体 句子:一串汉字和标点符号 语法:形成句子的规则 形式语言 字符 字母表 字符串 形式文法 字符串 字母表Σ: 非空的有穷集合 字符串: Σ中符号的有穷序列 如 Σ ={a,b} a, b, aab, babb 字符串ω的长度|ω|: ω中的字符个数 如 |a|=1, |aab|=3 空字符串ε: 长度为0, 即不含任何符号的字符串 an : n个a组成的字符串 Σ*: Σ上字符串的全体 子字符串(子串): 字符串中若干连续符号组成的字符串 前缀: 最左端的子串 后缀: 最右端的子串 例如 ω =abbaab a,ab,abb是ω的前缀 aab,ab,b是ω的后缀 ba是ω的子串, 但既不是前缀, 也不是后缀 ω本身也是ω的子串, 且既是前缀, 也是后缀 ε也是ω的子串, 且既是前缀, 也是后缀 字符串的连接运算 设α=a1a2 … an, β= b1b2 … bm, αβ=a1a2 … anb1b2 … bm称作α与β作的连接 如 α=ab, β=baa, αβ=abbaa, βα=baaab 对任意的字符串α, β, γ (1) (αβ)γ=α(βγ) 即, 连接运算满足结合律 (2) εα=αε=α 即, 空串ε是连接运算的单位元 n个α的连接记作αn 如 (ab)3= ababab, α0=ε 形式语言 定义: Σ*的子集称作字母表Σ上的形式语言, 简称 语言 例如 Σ={a,b} A={a,b,aa,bb} B={an | n∈N} C={anbm | n,m≥1} D={ε} 空语言? 形式文法 一个例子——标识符 标识符 : 字母 | 下划线 | 标识符 字母 | 标识符 下划线| 标识符数字 字母 : a | b | … | z | A | B | … | Z 下划线 : _ 数字 : 0 | 1 | … | 9 形式文法的定义 定义 形式文法是一个有序4元组G=V,T,S,P , 其中 (1) V是非空有穷集合, V 的元素称作变元或非终极符 (2) T是非空有穷集合且V∩T =?, T 的元素称作终极符 (3) S∈V 称作起始符 (4) P是非空有穷集合, P的元素称作产生式或改写规则, 形如α→β, 其中α,β∈(V∪T)*且α≠ε. 文法生成的语言 设文法 G = V,T,S,P, ω, λ∈(V∪T)*, ω ?λ: 存在α→β∈P和ξ,η∈(V∪T)*, 使得 ω= ξαη, λ= ξβη 称ω直接派生出λ. ω λ: 存在ω1, ω2, … , ωm, 使得 ω= ω1 ? ω2 ? … ? ωm= λ 称ω派生出λ. 恒有ω ω (当m=1时) 是 ? 的自反传递闭包 文法生成的语言 定义 设文法G= V,T,S,P , G生成的语言 L(G)={ω∈T* ∣S ω} L(G)由所有满足下述条件的字符串组成: (1) 仅含终结符; (2) 可由起始符派生出来. 定义 如果L(G1)= L(G2), 则称文法G1与G2等价. 举例 例1 文法G1= V,T,S,P,其中V={S}, T={a,b}, P: S→aSb | ab L(G1)={anbn | n0} 例2 文法G2= V,T,S,P,其中V={A,B,S}, T={0,1}, P: S→1A, A→0A | 1A | 0B, B→0 L(G2)={1x00 | x?{0, 1}*} 例3 文法G3= V,T,S,P,其中V={A,B,S}