电子科技大学：《有限自动机理论 Finite Automata Theory》课程教学资源（课件讲稿）第02章 形式语言简介

第二章形式语言简介 形式语言和自动机理论中的语言是 一个宽泛的概念（不同于传统语言)。 一个字母表上的语言就是该字母表 的任意字符串的集合。 语言中的字符串称为该语言的句子

第二章 形式语言简介 形式语言和自动机理论中的语言是 一个宽泛的概念（不同于传统语言）。 一个字母表上的语言就是该字母表 的任意字符串的集合。 语言中的字符串称为该语言的句子

语言的的定义可以从两个方面进行： 1)从产生语言的角度； 2)从接收（或识别）语言的角度

l 语言的的定义可以从两个方面进行： １）从产生语言的角度； ２）从接收(或识别)语言的角度

●产生语言 根据语言中的基本句子和其他句子的 形成规则，得到（产生）该语言所包含的 所有句子。 形式语言所研究的问题

l产生语言 根据语言中的基本句子和其他句子的 形成规则，得到(产生)该语言所包含的 所有句子。 l 形式语言所研究的问题

接收语言 使用自动机模型来接收字符串，接收 的所有字符串，也形成一个语言。 自动机所研究的问题

l接收语言 使用自动机模型来接收字符串，接收 的所有字符串，也形成一个语言。 l 自动机所研究的问题

统一的理论 形式语言与自动机作为统一的理论， 实际上包括3个方面的内容： )形式语言理论（产生语言） 2)自动机理论（接收语言） 3)形式语言与自动机的等价性理论

统一的理论 形式语言与自动机作为统一的理论, 实际上包括3个方面的内容: 1) 形式语言理论(产生语言) 2) 自动机理论(接收语言) 3) 形式语言与自动机的等价性理论

●本章介绍形式语言的基本内容

l 本章介绍形式语言的基本内容

语言的形式定义 设∑是一个字母表， Lc∑*，L称为字母表∑上的一个语言， w∈L,w称为语言L的一个句子

语言的形式定义 l 设是一个字母表， L* , L称为字母表上的一个语言, wL, w称为语言L的一个句子

2.1 例子语言 括号匹配串的语言。 该语言是指所有的左括号和右括号相 匹配的串的集合； (),(),（)()等等都是该语言的句子 )(,（)等等不是该语言的句子

2.1 例子语言 l括号匹配串的语言。 该语言是指所有的左括号和右括号相 匹配的串的集合； ( )，(( ))，( )( )等等都是该语言的句子 )( ，( ))等等不是该语言的句子

如何产生这个语言呢？ 即如何产生该语言所有句子呢？ ·递归方法提供了语言良好的定义方式

l 如何产生这个语言呢？ 即如何产生该语言所有句子呢？ l 递归方法提供了语言良好的定义方式

除基本句子外，其它句子按照相同的 方法（可能不止一种方法)产生 实际上，就是需要给出语言中所有句 子的形成规则（语法规则) ·可以使用多种方法描述形成规则

l 除基本句子外，其它句子按照相同的 方法（可能不止一种方法）产生 l 实际上，就是需要给出语言中所有句 子的 形成规则（语法规则） l 可以使用多种方法描述形成规则