形式语言和 自动机初步
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组成的字符串 Σ* : Σ上字符串的全体