《形式语言与自动机》课件绪论.ppt
《《形式语言与自动机》课件绪论.ppt》由会员分享,可在线阅读,更多相关《《形式语言与自动机》课件绪论.ppt(22页珍藏版)》请在文库网上搜索。
1、12023/6/7School of Computer Science,BUPT绪论绪论n 课程信息程信息n 为什么学什么学习形式形式语言与自言与自动机机n 形式形式语言与自言与自动机概述及机概述及应用用n 课程内容及要求程内容及要求22023/6/7School of Computer Science,BUPT 专业基基础课 -上世上世纪 60 60 年代末、年代末、7070年代初,年代初,研究的高峰研究的高峰-之后,向之后,向应用用领域渗透,域渗透,研究生研究生课程程-逐逐渐普及,普及,本科本科阶段的段的专业基基础课 专业工作者必工作者必须的理的理论素养素养 -计算模型算模型 计算机(不)
2、能算机(不)能够做什么做什么 -问题分分类 计算的复算的复杂性,算法分析性,算法分析 -形式系形式系统 建模工具(状建模工具(状态机机 )-抽象描述抽象描述 形式文法、形式表达式形式文法、形式表达式 课课 程程 性性 质质32023/6/7School of Computer Science,BUPT相 关 课 程先修先修课程程 -离散数学离散数学(数理(数理逻辑,集合,集合论)-计算机算机导论与程序与程序设计、数据、数据结构构 后后续课程程 -编译原理原理 其它相关其它相关课程程 模式模式识别、算法分析、算法分析 42023/6/7School of Computer Science,BUP
3、T为什么学习形式语言与自动机n形式形式语言与自言与自动机是机是计算机科学的基算机科学的基础理理论之一,是之一,是计算机学科的算机学科的专业基基础课。n在人工智能、在人工智能、电信信领域等有广泛的域等有广泛的应用。用。n通通过一一些些定定理理的的证明明和和应用用,对大大家家进行行思思维训练,从从而而为今今后后学学习通通信信软件件,协议工工程程,编译技技术,人人工工智智能能等等内内容容提提供供理理论基基础。形式语言与自动机概述及应用n本门课程将围绕着什么是形式语言、什么是自动机、以及形式语言和自动机的相互关系进行阐述。n核心内容核心内容n有限状态自动机,正规语言,正规表达式有限状态自动机,正规语言
4、,正规表达式n上下文无关文法,上下文无关语言,下推自动机上下文无关文法,上下文无关语言,下推自动机n 图灵机,计算问题分类图灵机,计算问题分类52023/6/7School of Computer Science,BUPT62023/6/7School of Computer Science,BUPT1形式语言n什么是形式什么是形式语言言n形式语言:形形式式化化描描述述的的字字母母表表上上的的字字符符串串的的集合。集合。n字母表:字符的有限集合。ne.g.:26个英文字母构成的字母表。n字符串:字母表中的字符构成的有限序列。ne.g.hello,afjhkfyu 72023/6/7School
5、 of Computer Science,BUPT为什么用形式语言为什么用形式语言n自自然然语言言:人人们平平时说话时所所使使用用的的一一种种语言,不同的国家和民族有着不同的言,不同的国家和民族有着不同的语言。言。n形式形式语言言n通通过人人们公公认的的符符号号,表表达达方方式式所所描描述述的的一一种种语言言,是是一一种种通通用用语言言,没没有有国国籍籍之之分。分。n形形式式语言言是是某某个个字字母母表表上上的的字字符符串串的的集集合合,有一定的描述范有一定的描述范围。82023/6/7School of Computer Science,BUPTn例例1:汉语:用用数字、符号等形式化的数字、
6、符号等形式化的东西来描述西来描述语言言n我吃我吃饭 语法正确法正确n我我饭吃吃 语法法错误n饭吃我吃我 语法正确,法正确,语义错误92023/6/7School of Computer Science,BUPTn例2:T为PASCAL语言所用的全部符号的集合。n正确的PASCAL程序就是T上的语言。n例3:在字母表T=a上,L=a 2n+1|n=0 n表示任意一对aa(包括0对)后跟一个a的字符串。(即含有奇数个a的字符串。)102023/6/7School of Computer Science,BUPTn形 式 语 言 的 最 初 起 因:语 言 学 家(Chomsky)想用一套形式化方法
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 形式语言与自动机 形式语言 自动机 课件 绪论