第二章 形式语言与文法1

S 推导出 “ 000111” ， 推导长度3
“ 000111” 归约到 S
+ 表示成 S ⇒ 000111
第2章 形式语言与文法 2.2 文法
2.2.3 相关概念
2．句型和句子
定义： 文法G（VN，VT，S ，P），若符号串x可由开始符号S推导出
* （S ⇒ x），则称 x 是 G 的一个句型，若x仅由终结符组成， 则称 x 为G 的一个句子。 注意：句型和句子都必须由开始符号S推出！
（2）用适当条数的规则描述了一个语言的全部句子。
第2章 形式语言与文法 2.1 语言
2.2 文法
2.2.1 文法的形式定义
2.2.2 文法的表示方法
2.2.3 相关概念
第2章 形式语言与文法
2.2 文法
2.2.1 文法的形式定义
1．终结符
不可分割的符号串，是组成句子的最基本的单位。
一个语言允许使用的所有终结符组成的集合称为终结符集， 用VT 表示。
则 |x|=4 , |y|=4 xy = “homework”
第2章 形式语言与文法
| xy | = 4+4 = 8
2.1 语言
2.1.1 语言的概念
方幂：符号串 x 的方幂就是 n个x 自身连接 次，表示为 xn 。 规定 x0 =ε。 成立的等式： x1=x ， x2=xx ， x3=xxx ，……
若n>0，则有： xn = xxn-1 = xn-1x
x* 表示 x 的任意多次方幂（可以是 0 次） x+ 表示 x 的任意非 0 次方幂。 【例2-3】 若 x = “ab” 则 x0 =ε x1 = “ab”
x2 = “abab”
第2章 形式语言与文法

2.3.3 语言的形式定义 1.直接推导 直接推导 是一文法， 直接推出x 令G是一文法，我们从 是一文法 我们从xAy直接推出 α y，即xAy ⇒ x α y，仅 直接推出 ， ， A → α是G的一个规则且 ∈ (VN∪ VT)*,也就是说从符号串 的一个规则且x,y 的一个规则且 也就是说从符号串 xAy直接推出 α y仅使用一次规则。 直接推出x 仅使用一次规则。 直接推出 仅使用一次规则 例：设有文法：G[E] 设有文法： 1、E → E+T|T 、 2、T → T∗F|F 、 ∗ 3、F →(E)|i 、 对从起始符号E到句子 到句子i+i∗ 的直接推导如下 对从起始符号 到句子 ∗i的直接推导如下 ： E⇒E+T⇒T+T⇒F+T⇒i+T⇒i+T∗F⇒i+F∗F ⇒ ⇒ ⇒ ⇒ ⇒ ∗ ⇒ ∗ ⇒i+i∗F⇒i+i∗i ∗ ⇒ ∗
8）符号串的幂 ） 定义： 是字母表上的符号串， 的幂运算为： 定义：设x是字母表上的符号串，则x的幂运算为： 是字母表上的符号串 的幂运算为 x0=ε， x1=x， x2=xx， … … ，xn=xn-1x(=x xn-1) ε ， ， 9）符号串集合的幂：（集合的相乘） ）符号串集合的幂：（集合的相乘） ：（集合的相乘 定义： 为符号串集合， 定义：若A为符号串集合，则符号串集合的幂为： 为符号串集合 则符号串集合的幂为： A0= {ε } ， A1=A ，A2=AA，… … ， An-1=An-2A， ε ， ， An=An-1A（=AAn-1）， （ 例：若A={a，b} ， 则 A1=A={a，b}； ， ；
2.3 文法和语言的形式定义 Σ：为某一字母表， L：一个语言， L⊂Σ 为某一字母表， ：一个语言， 字母表 ⊂Σ* ⊂Σ 2.3.1 形式语言 1.定义：序列的有穷集合。具体地说每个形式语言都是某个字母 定义：序列的有穷集合。 定义 表上按某种规则构成的所有符号串的集合， 表上按某种规则构成的所有符号串的集合，反之任何一个字母 表上符号串的集合均可以定义一个形式语言。 表上符号串的集合均可以定义一个形式语言。 2.表示方法： 表示方法： 表示方法 1）枚举法。当语言为有穷集合时使用。 ）枚举法。当语言为有穷集合时使用。 2）文法描述。当语言为无穷集合时使用。 ）文法描述。当语言为无穷集合时使用。

的情况。若从S出发，先用第一个产生式ｎ-1次，即S aSb
aaSbb … an-1S bn-1，最后再使用第二个产生式一次，得
到S
aｎbｎ，这个推导对于任何ｎ>1都是对的。再加上ｎ=1的
情况，即可得到L(G)＝{an bn∣n≥1 }。
文法语言
例2.9 给出文法G，它的产生式是：
S→aB∣bA
形式文法与形式语言
例2.4 下面的各四元组都是文法。
① G1 = ({A, B}, {0,1},{A→0B, B→1B, B→0}, A)。
② G2 =( {A,B,C},{a,b,C},{A→aBC, B→b, C→CC, C→ε}, A)。
③ G3=( {L,M,N}, {0,1,2}, { M→0LN, L→1, 0L→2, LN→12，N→0}，M)。
其他的符号如：iF,tHEn,ElsE,；,:=,<，>,+,-,*,/， a,b,C,x,y,z,等等都是构成语言的基本符号，也就是 字母表中的符号。
第五条规则关于<语句表>的定义，这是一种递归的 定义形式。
问题的提出
例2.2 根据例2.1中的各规则，我们指出下述的字符串 wHilE x≤5 Do x := (x+2) 是一个合法的语句。
形式文法与形式语言
例2.5 对例2.3 中 给出的文法用定义2. 1加以规范化。其四 元组表示就是： （{<SEntEnCE>，<Noun pHrasE>，<DEtErminEr>， <Noun>, <VErb pHrasE>, <VErb>}, {tHE, a, applE, Cat, man, Eats, sinGs, runs}, {<SEntEnCE>→<Noun pHrasE><VErb pHrasE>, <Noun pHrasE>→<DEtErminEr><Noun>, <DEtErminEr>→tHE, <DEtErminEr>→a, <Noun>→applE,<Noun>→Cat,<Noun>→man, <VErb pHrasE>→<VErb><Noun pHrasE>, <VErb pHrasE>→<VErb>, <VErb>→Eats,<VErb>→sinGs,<VErb>→runs}, <SEntEnCE>）

例2-5
C语言中简单变量的说明语句的定义。 C语言中的说明语句形式为：
TYPE 变量名表； TYPE 变量名表； … TYPE 变量名表；
产生式为：
S→SS|P P→T V； T→int|char|float V→V,V|I I→L|IL|ID L→a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p| q|r|s|t|u|v|w|x|y|z D→0|1|2|3|4|5|6|7|8|9
符号“( ”和“ )”是字母表的元素。
Chomsky采用的符号化(形式化)的 描述方式，运用如下的规则（这些规 则被称为产生式）：
① S→( )
② S→(S)
③ S→SS
→”读作“定义为”或者“是” ，它 的左边和右边分别称为该产生式的左 边和右边；
根据这些规则，也可以生 成任意合法的串；可以判 断一个串是否为合法的串。
语言就是某个字母表上的字符串组成的一 个集合。语言中的字符串称为句子。
文法的作用就是产生一个语言。
有穷语言的表示较容易，即使语言中的句 子的组成没有什么规律，也可以使用枚举 的方式列出语言中的所有句子。
对于无穷语言，使用有穷描述的方式表达。 需要从语言包含的句子的一般构成规律去 考虑问题。这种从语言的有穷描述来表达 语言的方法对一般的语言都是有效的。尤 其在使用计算机判断一个字符串是否是某 个语言的句子时，从句子和语言的结构特 征上着手是非常重要的。
考虑：
由奇数个1组成串的语言的产生。
例2-3：包含有+、-பைடு நூலகம்*、/、 （）的算术表达式的语言。
自然语言的描述方式
①单个变量是合法的最基本的串； ②若S是一个合法的串，则SAS是一
个合法的串（ 其中A代表运算符+、 -、*、/） ③若S是一个合法的串，则(S)是合法 的串；

语言的语法结构
总结词
语言的语法结构是语言形成和发展的核心要素，决定 了语言的表达方式和意义。
详细描述
语言的语法结构是指语言的组织规律和规则，包括词 法、句法、语义等方面的规则。词法规定了词汇的构 成和变化规则，如名词、动词、形容词等词类的划分 ；句法规定了句子结构的规则，如主语、谓语、宾语 等句子的成分及其排列顺序；语义则涉及到词汇和句 子的意义和解释。语言的语法结构是语言理解和生成 的基础，也是语言演变和发展的关键因素。
文法和语言的应用前景
1 2
人工智能领域
文法和语言是人工智能领域的重要基础，可用于 自然语言处理、机器翻译、语音识别等技术的研 究和应用。
计算机科学教育
文法和语言是计算机科学专业的重要课程之一， 对于培养计算机科学人才具有重要意义。
3
软件工程领域
文法和语言可用于软件工程领域中的编译器设计 和开发，提高软件开发的效率和可靠性。
05
文法和语言的未来发展
文法和语言的研究方向
形式语言理论
深入研究形式语言的基本理论， 包括语法、语义和语用等方面， 为自然语言处理和人工智能等领 域提供理论基础。
自然语言处理
结合自然语言处理技术，研究自 然语言的语法、语义和语用规律， 提高自然语言处理的准确性和效 率。
计算语言学
将计算语言学与形式语言理论相 结合，研究语言处理算法和模型， 为机器翻译、语音识别等领域提 供技术支持。
文法和语言的发展趋势
深度学习与文法和语言的结合
01
随着深度学习技术的发展，文法和语言的研究将更加注重与深
度学习的结合，以提高语言处理的性能和效率。
跨媒体语言处理
02
随着多媒体数据的普及，文法和语言的研究将逐渐扩展到跨媒

2011年6月7日
推导方法： 推导方法：从一个要识别的符号 开始推导， 开始推导，即用相应规则的 右部来替代规则的左部， 来替代规则的左部 右部来替代规则的左部， 每次仅用一条规则去进行推导。 每次仅用一条规则去进行推导。
<句子 ::=<主语><谓语> 句子>::=<主语><谓语> 句子 ::=<主语><谓语 >::=<代词>|<名词 <主语>::=<代词>|<名词> 主语>::=<代词>|<名词> <代词> ::=你|我|他 代词> ::=你 名词>::= 王民|大学生|工人| <名词>::= 王民|大学生|工人|英语 >::=<动词><直接宾语 <谓语>::=<动词><直接宾语> 谓语>::=<动词><直接宾语> >::=是 <动词>::=是|学习 动词>::= 直接宾语>::=<代词>|<名词> >::=<代词>|<名词 <直接宾语>::=<代词>|<名词>
2011年6月7日
2.由规则推导句子：有了一组规则之后， 2.由规则推导句子：有了一组规则之后，可以按照一定的方式 由规则推导句子 用它们去推导或产生句子。 用它们去推导或产生句子。 推导方法：从一个要识别的符号开始推导， 推导方法：从一个要识别的符号开始推导，即用相应规则的 右部来替代规则的左部，每次仅用一条规则去进行推导。 来替代规则的左部 右部来替代规则的左部，每次仅用一条规则去进行推导。 <句子 => <主语><谓语> 句子> <主语><谓语 主语><谓语> 句子 <代词><谓语 代词><谓语> <主语><谓语> => <代词><谓语> 主语><谓语> ><谓语 …… …… 这种推导一直进行下去，直到所有带< >的符号都由终结符号 这种推导一直进行下去，直到所有带< >的符号都由终结符号 替代为止。 替代为止。

xxx
x y x+y
关于字符串的运算
其它 如 取头字符，取尾部，子串匹配 等 设ω1, ω2, ω3是字母表T上的字符串，称：
ω1是字符串ω1ω2的前缀， ω2是字符串ω1ω2的后缀， ω2是字符串ω1ω2ω3的子串。 空串是任何字符串的前缀，后缀及子串。 例：abc的前缀 a ab abc ε.
举例 = 0， bbaba = 5
ai 表示含有i个a的字符串
关于字符串的运算
连接（concatenation） 设 x, y为串, 且 x a1a2 … am, y b1b2 … bn, 则 x 与 y 的连接 x y a1a2 … am b1b2 … bn
连接运算的性质 ( x y ) z x（ y z ）
隐含的概念：如何表述子集的“特性和规则”，
举例 - 左右括号的匹配。
英文单词集 …, English, …, words , … C 语言程序集 … 字母表？ 汉语成语集 …, 马到成功, … 化学分子式集 …, H2O, …, NaCl , … any, 任意
语 言 （Languages）
举例：设T = {a，b} 则 L1 = {anbn | n≥1} L3 = { bk | k 是质数} L2 ={ε} 只有一个空句子的语言 L4 = { } = Φ 空语言 均为字母表T上的语言。
由语言的定义知语言是集合，对于集合的运算可 应用于对于语言的计算。如并，交，补，差。
语言的基本运算
字 符 串 （string）
概念 字母表 T 上的一个字符串（简称串），或称为 字（word），为 T 中字符构成的一个有限序列。
空串（empty string）, 用 表示，不包含任何
字符。

即：E=>＊ (i*i+ i) 所以,符号串(i*i+i)是文法G[E]的一个句子。
三、语言的形式定义：


定义：由文法G[S]产生的所有句子的集合。 即： L(G[S]) = {x|S=>+x,且x∈V*} T 注：
① 一旦文法给定，语言就确定。 ② 语言L(G)是V*的子集。（语言是字母表中终结 T
符号串闭包的子集）
即：属于L(G)的句子属于V* T 反之,属于V*的符号串x不一定属于L(G)。 T
例：已知文法G[S]： S::=0S1|01 求:L(G)=? 解：分析：S=>0S1 =>00S11 =>000S111 … =>0n-1S1n-1 =>0n1n 即：S=>＊0n1n ∴G描述的语言：L(G[S]) = {0n1n | n≥1 } 但： ＋ VT’＝{0,1,00,01,10,11,000,…,111,0000,…,0011,…,1111,…}， ＋ 可见L(G)仅是VT‘的真子集。
定义：字母表中的元素.
注:符号是字母表中不可再分解的最小单位.
3. 符号串
定义：字母表中的符号组成的有穷序列. 例:∑={a, b, c} 符 号:a, b, c 符号串:a, b, c, ab, ac, aa, ba, ca, abc, … 例;设字母表A={0, 1} A中的符号:0, 1 A中的符串:0,1,01,10,00,11,001,010, …,01000, …
注：{ε }A=A{ε}=A A=A =A (其中 为空集)
注: ε 不属于 ={ }
， 即空符号串并不属于空集
4.符号串集合的方幂
设A为符号串集合,则定义 1 2 0 A={ε} A=A A=AA 3 2 2 A=AA=AA=AAA

2019/2/21 22
四、文法和语言分类（续三）
3、3型文法与3型语言 定义:文法G中的每个规则若为A::= B（ A::= B ）或A::= ,A，B Vn, VT,则称G是3型文法,3型文法确定的语言 为3型语言,表示为L3. 3型文法又称为正则文法或正规文法(regular grammar).由正 则文法确定的语言称为正则语言。 适合描述高级语言中词法相关部分。 正 则 文 法
二、基本概念（续一）
2.符号串的运算 符号串相等：符号串x，y，如果两者诸符号依次相等， 则两符号相等。 符号串的长度：符号串中包含符号的个数。 |abc|=3；| |=0； 符号串的连结：x，y是字母表上的两个字符串，把y的 所有符号相继写在x的符号之后所得到的符号串称为x与 y的连结，用xy表示。 X=abc，y=def 则xy=abcdef；yx=defabc；xy yx x=x =x； 符号串的逆:设x是字母表上的符号串，其逆为符号串x ~ ~ 2019/2/21 的倒置，记为x。x=abcd；x=dcba； 5

2019/2/21
15
三、文法（续五）
推导： 如果a1可直接推导出 a2， a2可直接推导出a3，…… an-1可直 接推导出an，即存在一个自a1到an的直接推导序列 a1 a2 a3 … an-1 an(n>0) 则称a1可推导出an,记作a1 an +表示从a1出发经过一步或若 干步，可推导出an，这个推导长度为n-1；
2019/2/21
3
二、基本概念
1。字母表和符号串 字母表: 一个非空的有穷集合. V={0,1} 符号: 字母表中的元素称为符号或字符 符号串: 符号的有穷序列称为符号串. eg.字母表={a,b,c,d} 则有符号串:a,b,c,d,aa,ddd,acc… 注意:表示空符号串,它表示不包含任何符号串.不是空 格符.符号串中的符号是有顺序的. 符号串集合: 字母表上若干个符号串组成的集合. A={ab,acc,da,a}; 约定:小写字母 a,b,…,r表示符号. 小写字母: s,t,…,z表示字符串; 大写字母:A,B,..,Z表示字符串集合; 2019/2/21 4