形式语言—文法课件

2013-7-25
8
2.1 启示
<名词短语>中国 <名词短语>教育 <名词短语>集合 <名词短语> WTO <名词短语>美丽的城市 <名词短语>祖国的首都 <名词短语>数学的基础 <名词短语>社会发展的前面 <句号>。
2013-7-25 9
ห้องสมุดไป่ตู้
2.1 启示
• 表示一个语言，需要4种东西 ⑴形如<名词短语>的 “符号”
2013-7-25
1
第2章 文法
• 主要内容
文法的直观意义与形式定义，推导、文法产生 的语言、句子、句型；乔姆斯基体系，左线性文 法、右线性文法，文法的推导与归约；空语句。
• 重点
文法、推导、归约、模型的等价性证明。
• 难点
形式化的概念，文法的构造。
2013-7-25 2
2.1 启示
• 文法的概念最早是由语言学家们在研究自然语言 理解中完成形式化。 • 归纳如下句子的描述： ⑴ 哈尔滨是美丽的城市。 ⑵ 北京是祖国的首都。 ⑶ 集合是数学的基础。 ⑷ 形式语言是很抽象的。 ⑸ 教育走在社会发展的前面。 ⑹ 中国进入WTO。
2013-7-25 18
2.2 形式定义
•例 2-3 四元组是否满足文法的要求。
– ({A，B，C，E}，{a，b，c}，{SABC|abc，De|a，
FBc，AA，E abc|ε }，S) – 4种修改
(1) ({A，B，C，E，S，D，F}，{a，b，c，e}， {SABC|abc，De|a，FBc，AA，E abc|ε }， S)。 (2) ({A，B，C，E，S }，{a，b，c}，{SABC|abc， AA，E abc|ε }，S)。 (3) ({A，B，C，E}，{a，b，c}，{ AA，E abc|ε }，A)。 (4) ({A，B，C，E}，{a，b，c}，{ AA，E abc|ε }，E)。
2013-7-25
25
2.2 形式定义
A aA aaA aaaA aaaaA … a…aA a…aaA
2013-7-25
使用产生式AaA 使用产生式AaA 使用产生式AaA 使用产生式AaA 使用产生式AaA 使用产生式AaA
26
2.2 形式定义
AAaaAAA AAaaAaAA AaAaaAaAA AaAaaAaaA aaAaaAaaA aaAaaAaaa aaaAaaAaaa aaaaaaAaaa aaaaaaaaaa
2013-7-25
17
2.2 形式定义
⑵ 使用符号 • 英文字母表较为前面的大写字母，如A，B，C，… 表示语法变量； • 英文字母表较为前面的小写字母，如a，b，c，… 表示终极符号； • 英文字母表较为后面的大写字母，如X，Y，Z，… 表示该符号是语法变量或者终极符号； • 英文字母表较为后面的小写字母，如x，y，z，… 表示由终极符号组成的行； • 希腊字母α ，β ，γ …表示由语法变量和终极符号 组成的行
2013-7-25
14
2.2 形式定义
• 例 2-1 以下四元组都是文法。
⑴ ({A}，{0，1}，{A01，A0A1，A1A0}，A)。 ⑵ ({A}，{0，1}，{A0，A0A}，A)。 ⑶ ({A，B}，{0，1}，{A01，A0A1，A1A0，BAB， B0}，A)。 ⑷ ({A，B}，{0，1}，{A0，A1，A0A，A1A }， A)。
2013-7-25 19
2.2 形式定义
• 推导(derivation)
设G=(V，T，P，S)是一个文法，如果α β ∈P， γ ，δ ∈(V∪T)*，则称γ α δ 在G中直接推导 出γ β δ 。 γ α δ γ β δ G
读作：γ α δ 在文法G中直接推导出γ β δ 。 “直接推导”可以简称为推导(derivation)，也 称推导为派生。
2013-7-25
22
2.2 形式定义
+ 当成(V∪T)*上的二元关系。 * G、 G、 G n (1)Α β ：表示α 在G中经过n步推导出β ； G β 在G中经过n步归约成α 。即，存在α 1， α 2，…，α n-1∈(V∪T)*使得α α 1， G α 1α 2，…，α n-1β 。 G G 0 (2)当n=0时，有α =β 。即α α 。 G + (3)α β ：表示α 在G中经过至少1步推导出β ； G β 在G中经过至少1步归约成α 。
12
2.2 形式定义
– T——为终极符(terminal)的非空有穷集。 a∈T，a叫做终极符。由于V中变量表 示语法范畴，T中的字符是语言的句子中 出现的字符，所以，有V∩T=Φ 。 – S——S∈V，为文法G的开始符号(start symbol)。
2013-7-25
13
2.2 形式定义
– P——为产生式(production)的非空有穷 集合。P中的元素均具有形式α β ， 被称为产生式，读作：α 定义为β 。其 中α ∈(V∪T)+，且α 中至少有V中元素 的一个出现。β ∈(V∪T)*。α 称为产生 式α β 的左部，β 称为产生式α β 的右部。产生式又叫做定义式或者语法 规则。
2013-7-25 29
2.2 形式定义
例2-6 设G=({A}，{0，1}，{A01，A0A1}，A)， n n n A 0 A1 n≥0 0nA1n 0n+1A1n+1 n≥0 0nA1n 0n+11n+1 n≥0 i+1 0nA1n 0n+iA1n+i n≥0，i≥0 i nA1n 0n+i1n+i 0 n≥0，i≥0 * 0nA1n 0mA1m n≥0，m≥n + nA1n 0m1m 0 n≥0，m≥n+1 + nA1n 0mA1m 0 n≥0，m≥n+1 + 0nA1n 0m1m n≥0，m≥n+1
2013-7-25 30
2.2 形式定义
• 几点结论
– 对任意的x∈∑+，我们要使语法范畴D代表的 集合为{xn|n≥0}，可用产生式组{Dε |xD}来 实现。 – 对任意的x，y∈∑+，我们要使语法范畴D代表 的集合为{xnyn|n≥1}，可用产生式组 {Dxy|xDy}来实现。 – 对任意的x，y∈∑+，我们要使语法范畴D代表 的集合为{xnyn|n≥0}，可用产生式组 {Dε |xDy}来实现。
• <动词短语>可以是<动词><形容词短语> 或者<动 词><名词短语> 。 • <名词短语>={北京、哈尔滨、形式语言、中国、 教育、集合、WTO、美丽的城市、祖国的首都、 数学的基础、社会发展的前面}。 • <动词>={是、走在、进入}。 • <形容词短语>={很抽象的}。 • 把<名词短语><动词短语><句号>取名为<句子>。
2013-7-25
16
2.2 形式定义
• 约定
⑴ 对一组有相同左部的产生式 α β 1，α β 2 ，… ，α β n 可以简单地记为： α β 1|β 2|…|β n 读作：α 定义为β 1，或者β 2，…，或者β n。并 且称它们为α 产生式。β 1，β 2，…，β n称为 候选式(candidate)。
2013-7-25 3
2.1 启示
• 6个句子的主体结构
<名词短语><动词短语><句号> <名词短语>={哈尔滨，北京，集合，形式语言， 教育，中国} <动词短语>={是美丽的城市，是祖国的首都，是 数学的基础，是很抽象的，走在社会发展的前 面，进入WTO} <句号>={。}
2013-7-25
4
2.1 启示
2013-7-25
使用产生式AaA 使用产生式AaA 使用产生式Aa 使用产生式Aa 使用产生式Aa 使用产生式AaA 使用产生式Aa 使用产生式Aa
27
2.2 形式定义
• 例 2-5 设G=({S，A，B}，{0，1}， {SA|AB，A0|0A，B1|11}，S) 对于n≥1， n A 0n 首先连续n-1次使用产生式； A0A， 最后使用产生式A0； n A 0 nA 连续n次使用产生式A0A； B1 使用产生式B1； B 11 使用产生式B11。
2013-7-25
5
2.1 启示
2013-7-25
6
2.1 启示
• 表示成α β 形式
<句子><名词短语><动词短语><句号> <动词短语><动词><形容词短语> <动词短语><动词><名词短语> <动词>是
2013-7-25
7
2.1 启示
<动词>走在 <动词>进入 <形容词短语>很抽象的 <名词短语>北京 <名词短语>哈尔滨 <名词短语>形式语言
2013-7-25 20
2.2 形式定义
• 归约(reduction) – γ α δ γ β δ G
– 称γ β δ 在文法G中直接归约成γ α δ 。在不 特别强调归约的直接性时，“直接归约”可以 简称为归约。
2013-7-25
21
2.2 形式定义
1． 推导与归约表达的意思的异同。 2． 推导与归约和产生式不一样。所以，G和 所表达的意思不一样。 3． 推导与归约是一一对应的。 4． 推导与归约的作用。