形式语言和 自动机初步
1 形式语言和 自动机初步
第11章形式语言和自动机初步 ■11形式语言和形式文法 ■112有穷自动机 13有穷自动机和正则文法的等价性 ■114图灵机
2 第11章 形式语言和自动机初步 ◼ 11.1 形式语言和形式文法 ◼ 11.2 有穷自动机 ◼ 11.3 有穷自动机和正则文法的等价性 ◼ 11.4 图灵机
111形式语言与形式文法 ■字符串和形式语言 ■形式文法 ■形式文法的分类 口0型文法 口1型文法或上下文有关文法 口2型文法或上下文无关文法 口3型文法或正则文法
3 ◼ 字符串和形式语言 ◼ 形式文法 ◼ 形式文法的分类 0型文法 1型文法 或上下文有关文法 2型文法 或上下文无关文法 3型文法 或正则文法 11.1 形式语言与形式文法
语言的基本要素 汉语 形式语言 字符:汉字和标点符号 字符 字符集:合法字符的全体 字母表 句子:一串汉字和标点符号字符串 语法:形成句子的规则 形式文法
4 语言的基本要素 汉语 字符:汉字和标点符号 字符集:合法字符的全体 句子:一串汉字和标点符号 语法:形成句子的规则 形式语言 字符 字母表 字符串 形式文法
字符串 字母表∑:非空的有穷集合 字符串:∑中符号的有穷序列 如∑={a,b} a.b. aab. babb 字符串o的长度|o:o中的字符个数 如|al=1,|aab=3 空字符串E:长度为0,即不含任何符号的字符串 mn:n个a组成的字符串 x:∑上字符串的全体
5 字符串 字母表Σ: 非空的有穷集合 字符串: Σ中符号的有穷序列 如 Σ ={a,b} a, b, aab, babb 字符串ω的长度|ω|: ω中的字符个数 如 |a|=1, |aab|=3 空字符串ε: 长度为0, 即不含任何符号的字符串 a n : n个a组成的字符串 Σ* : Σ上字符串的全体
子字符串(子串) 字符串中若干连续符号组成的字符串 前缀:最左端的子串 后缀:最右端的子串 例如o= abbas a,ab,abb是o的前缀 ab,ab,b是o的后缀 bd是的子串,但既不是前缀,也不是后缀 O本身也是o的子串,且既是前缀,也是后缀 e也是o的子串,且既是前缀,也是后缀
6 子字符串(子串): 字符串中若干连续符号组成的字符串 前缀: 最左端的子串 后缀: 最右端的子串 例如 ω =abbaab a,ab,abb是ω的前缀 aab,ab,b是ω的后缀 ba是ω的子串, 但既不是前缀, 也不是后缀 ω本身也是ω的子串, 且既是前缀, 也是后缀 ε也是ω的子串, 且既是前缀, 也是后缀
字符串的连接运算 设∝=an1a2…anP=b1b2…,b, aB=a1a2…,anb1b2…b称作a与B作的连接 tn a=ab, B=baa, aB=abba, Ba=baaab 对任意的字符串a,B, (1)(oB)=∞(6y) 即,连接运算满足结合律 (2) C=8=0 即,空串E是连接运算的单位元 n个a的连接记作c 如(ab)}= ababab
7 字符串的连接运算 设α=a1a2 …an , β= b1b2 … bm, αβ=a1a2 …anb1b2 … bm称作α与β作的连接 如 α=ab, β=baa, αβ=abbaa, βα=baaab 对任意的字符串α, β, γ (1) (αβ)γ=α(βγ) 即, 连接运算满足结合律 (2) εα=αε=α 即, 空串ε是连接运算的单位元 n个α的连接记作α n 如 (ab) 3= ababab, α 0=ε
形式语言 定义:∑的子集称作字母表上的形式语言, 简称语言 例如x={a,b} A={,b,,bb} B={n|n∈N Cabin,m21y D={e} 空语言O
8 形式语言 定义: Σ*的子集称作字母表Σ上的形式语言, 简称 语言 例如 Σ={a,b} A={a,b,aa,bb} B={a n | n∈N} C={a nb m | n,m≥1} D={ε} 空语言Ø
形式文法 个例子标识符 :|| :a|b|….|z|A|B|….|Z : :0|11….9
9 形式文法 一个例子——标识符 : | | | | : a | b | … | z | A | B | … | Z : _ : 0 | 1 | … | 9
形式文法的定义 定义形式文法是一个有序4元组G=, 其中 (1)V是非空有穷集合,V的元素称作变元或非终极符 (2)T是非空有穷集合且M∩T=0,T的元素称作终极符 (3)S∈v称作起始符 (4)P是非空有穷集合,P的元素称作产生式或改写规则, 形如a→,其中a2∈(UUT*且a+t 10
10 形式文法的定义 定义 形式文法是一个有序4元组G=, 其中 (1) V是非空有穷集合, V 的元素称作变元或非终极符 (2) T是非空有穷集合且V∩T =Ø, T 的元素称作终极符 (3) S∈V 称作起始符 (4) P是非空有穷集合, P的元素称作产生式或改写规则, 形如α→β, 其中α,β∈(V∪T)*且α≠ε