电子科技大学：《形式语言与自动机》第二章 文法与语言

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

第二章 文法与语言 ⚫ 一个语言的定义可以从两个方面进行： ⚫ 从语言产生的角度；（形式语言） ⚫ 从接收(识别)语言的角度。（自动机）

设∑是一个字母表,VLc∑,L称为 字母表∑上的一个语言( language), X∈L,X叫做L的一个句子

⚫ 设是一个字母表，L  * , L称为 字母表上的一个语言(language), x  L, x叫做L的一个句子

21例子语言 例1:括号匹配的语言(该语言是指 所有的左、右括号相匹配的串的集 合)。 ●问题:如何产生该语言?即如何生 成该集合中的所有的串?

2.1 例子语言 ⚫例1：括号匹配的语言(该语言是指 所有的左、右括号相匹配的串的集 合)。 ⚫问题：如何产生该语言？即如何生 成该集合中的所有的串？

●自然语言的描述方式,采用如下的 递归规则: ①()是合法的该语言的最基本的串; ②若S是一个合法的串,则(S是合法串; ③若S是一个合法的串,则SS是合法串;

⚫ 自然语言的描述方式，采用如下的 递归规则： ①( )是合法的该语言的最基本的串； ②若S是一个合法的串,则(S)是合法串； ③若S是一个合法的串,则SS是合法串；

●这些规则称为形成规则,根据这些规 则,可以 (1)产生任意合法(即符合规则)的该 集合中的串; (2)判断某个串是否是合法的该集合的 串(即合法的句子)

⚫这些规则称为形成规则，根据这些规 则，可以 ⚫ (1)产生任意合法（即符合规则）的该 集合中的串； ⚫ (2)判断某个串是否是合法的该集合的 串（即合法的句子）

例如:可以产生串(()); 而推断串 (())) 不是合法的串

⚫例如： 可以产生串（（））； 而推断串 （（））） 不是合法的串

规则(的个数)是有限的,但可 以产生无限个串和无限长度 的串; ●因为规则是递归的

⚫规则(的个数)是有限的，但可 以产生无限个串和无限长度 的串； ⚫因为规则是递归的

●巴科斯和诺尔采用的巴科斯-诺尔范式(BNF Backus- Naur Forn)描述规则: :=() ●:= ●:=()

⚫ 巴科斯和诺尔采用的巴科斯-诺尔范式（BNF-- Backus-Naur Form）描述规则： ⚫ ::= ( ) ⚫ ::= ⚫ ::=()

●使用尖括号“”包括起来的部分,作 为一个整体来看待,表示某个语法成分,最 终,需要使用字母表中的字母来定义。 符号“∷=”是BNF本身的符号(元符号), 代表“定义为”或“就是”。 ●符号“(”和“)”是字母表的元素

⚫ 使用尖括号“”包括起来的部分，作 为一个整体来看待，表示某个语法成分，最 终，需要使用字母表中的字母来定义。 ⚫ 符号“::=”是BNF本身的符号（元符号）， 代表“定义为”或“就是” 。 ⚫ 符号“( ”和“ )”是字母表的元素

o Chomsky釆用的符号化(形式化)的 描述方式,运用如下的规则(这些规 则被称为产生式) ①S→( ②S→(S) ③S→Ss

⚫ Chomsky采用的符号化(形式化)的 描述方式，运用如下的规则（这些规 则被称为产生式）： ① S→( ) ② S→(S) ③ S→SS