一、字符串和形式语言 二、形式文法 三、形式文法的分类

◼ 课程信息 ◼ 为什么学习形式语言与自动机 ◼ 形式语言与自动机概述及应用 ◼ 课程内容及要求

本章将对形式语言和有限自动机理 论中所需的数学基础知识作扼要的 介绍。内容包括集合及其运算、关 系、证明的方法、图与树的概念 以及一些常用术语和形式语言与自 动机的发展

一、一个语言的定义可以从两个方面进行: 二、从语言产生的角度;(形式语言) 三、从接收(识别)语言的角度。(自动机)

自然语言是人与人交流思想的工具，程序语言是人和计算机之间传达信息的工具。为了描述程序语言，本章将引进有关形式语言的基本概念。文法是程序语言的生成系统，自动机是程序语言的识别系统，用文法来精确定义一个语言，然后根据这个文法构造识别这个语言的自动机，因此文法对程序语言和编译程序的构造来说意义重大。随着计算机的发展，形式语言学发展很快。N.Chomsky将文法分成四类，程序语言的词法可用正规文法描述，语法可用上下文无关文法描述，语义则要借助于上下文有关文法来描述。因此我们的注意力是针对这几类文法，特别是上下文无关文法

在第一章中已指出对于程序的语法分析和自然 语言的处理,形式化的文法描述方式起了重要 的作用。本章介绍Chomsky的文法体系,语 言的运算和运算的封闭性

一、图灵机的基本模型 二、图灵机接受的语言——递归可枚举语言 三、用图灵机计算函数——部分可计算函数与可计算函数

◼ 定义形式语言的术语 ◼ 给出文法的定义和文法的分类

1.1 集合及其运算 1.2 关系 1.3 证明和证明的方法 1.4 图与树 1.5 语言 1.6 常用术语 1.7 形式语言与自动机的发展

南京大学：《形式语言与自动机 Formal Languages and Automata》课程教学资源（PPT课件讲稿）Finite Automata