文档介绍：形式语言与自动机
陈文宇
电子科技大学计算机科学与工程学院
******@uestc.
教材:
形式语言与自动机
(陈文宇欧齐程炼)
人民邮电出版社
参考书:
形式语言与自动机理论
(蒋宗礼清华大学出版社)
形式语言与自动机
(陈有祺南开大学出版社)
形式语言和自动机的理论是计算机科学的理论基础。这些理论来源于
(1) Chomsky对自然语言的研究;
(2) ALGOL 60语言的语法描述方式;
(3)Kleene对自动机的研究;
早在20世纪五十年代,在研究如何使“自然语言”符号化(即形式化)的过程中,产生并发展了“形式语言与自动机”的理论。不久,人们就发现该理论与计算机科学中所创立和使用的程序设计语言具有密切的关系(比如,可以用于描述程序设计语言的词法和语法规则)。从此以后,形式语言与自动机的理论和方法的研究,受到了越来越多科学家的重视。
形式语言和自动机的理论已经成为计算机科学的理论基础,其应用范围已被扩展到生物工程、自动控制系统、图象处理与模式识别等许多领域。
实际上,“形式语言与自动机”的理论除了在计算机科学领域中的直接应用外,对于计算机科学人才的计算思维能力的培养,具有重要作用。
形式化描述和抽象思维能力,逻辑思维方法。这种能力就是计算思维能力或计算机思维能力。
第1章绪论
本章将对形式语言和有限自动机理论中所需的数学基础知识作扼要的介绍。内容包括集合及其运算、关系、证明的方法、图与树的概念;以及一些常用术语和形式语言与自动机的发展。
第1章绪论
关系
证明和证明的方法
图与树
语言
常用术语
形式语言与自动机的发展
一些没有重复的对象的全体称为集合(set),而这些被包含的对象称为该集合的元素(element)。
集合中元素可以按任意的顺序进行排列。一般,使用大写英文字母表示一个集合。