形式语言第2章文法

《形式语言第2章文法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2021/8/81第2章文法对任何语言L，有一个字母表∑，使得L∑*。L的具体组成结构是什么样的？一个给定的字符串是否为一个给定语言的句子?如果不是，它在结构的什么地方出了错？进一步地，这个错误是什么样的错？如何更正？……。这些问题对有穷语言来说，比较容易解决。这些问题对无穷语言来说，不太容易解决。语言的有穷描述。2021/8/82第2章文法主要内容文法的直观意义与形式定义，推导、文法产生的语言、句子、句型；乔姆斯基体系，左线性文法、右线性文法，文法的推导与归约；空语句。重点文法、推导、归约、模型的等价性证明。难点形式化的概念，文法的构造。2021/8/832.1启

2、示文法的概念最早是由语言学家们在研究自然语言理解中完成形式化。归纳如下句子的描述：⑴哈尔滨是美丽的城市。⑵北京是祖国的首都。⑶集合是数学的基础。⑷形式语言是很抽象的。⑸教育走在社会发展的前面。⑹中国进入WTO。2021/8/842.1启示6个句子的主体结构<名词短语><动词短语><句号><名词短语>={哈尔滨，北京，集合，形式语言，教育，中国}<动词短语>={是美丽的城市，是祖国的首都，是数学的基础，是很抽象的，走在社会发展的前面，进入WTO}<句号>={。}2021/8/852.1启示<动词短语>可以是<动词><形容词短语>或者<动词><名词短语>。<名词短语>={

3、北京、哈尔滨、形式语言、中国、教育、集合、WTO、美丽的城市、祖国的首都、数学的基础、社会发展的前面}。<动词>={是、走在、进入}。<形容词短语>={很抽象的}。把<名词短语><动词短语><句号>取名为<句子>。2021/8/862.1启示2021/8/872.1启示表示成αβ形式<句子><名词短语><动词短语><句号><动词短语><动词><形容词短语><动词短语><动词><名词短语><动词>是2021/8/882.1启示<动词>走在<动词>进入<形容词短语>很抽象的<名词短语>北京<名词短语>哈尔滨<名词短语>形式语言2021/8/892.1

4、启示<名词短语>中国<名词短语>教育<名词短语>集合<名词短语>WTO<名词短语>美丽的城市<名词短语>祖国的首都<名词短语>数学的基础<名词短语>社会发展的前面<句号>。2021/8/8102.1启示表示一个语言，需要4种东西⑴形如<名词短语>的“符号”它们表示相应语言结构中某个位置上可以出现的一些内容。每个“符号”对应的是一个集合，在该语言的一个具体句子中，句子的这个位置上能且仅能出现相应集合中的某个元素。所以，这种“符号”代表的是一个语法范畴。⑵<句子>所有的“规则”，都是为了说明<句子>的结构而存在，相当于说，定义的就是<句子>。2021/8

5、/8112.1启示⑶形如北京的“符号”它们是所定义语言的合法句子中将出现的“符号”。仅仅表示自身，称为终极符号。⑷所有的“规则”都呈αβ的形式在产生语言的句子中被使用，称这些“规则”为产生式。2021/8/8122.2形式定义文法(grammar)G=(V，T，P，S)V——为变量(variable)的非空有穷集。A∈V，A叫做一个语法变量(syntacticVariable)，简称为变量，也可叫做非终极符号(nonterminal)。它表示一个语法范畴(syntacticCategory)。所以，本文中有时候又称之为语法范畴。2021/8/8132.2形式定义T

6、——为终极符(terminal)的非空有穷集。a∈T，a叫做终极符。由于V中变量表示语法范畴，T中的字符是语言的句子中出现的字符，所以，有V∩T=Φ。S——S∈V，为文法G的开始符号(startsymbol)。2021/8/8142.2形式定义P——为产生式(production)的非空有穷集合。P中的元素均具有形式αβ，被称为产生式，读作：α定义为β。其中α∈(V∪T)+，且α中至少有V中元素的一个出现。β∈(V∪T)*。α称为产生式αβ的左部，β称为产生式αβ的右部。产生式又叫做定义式或者语法规则。2021/8/8152.2形式定义例2-1以下四元组都是文

7、法。⑴({A}，{0，1}，{A01，A0A1，A1A0}，A)。⑵({A}，{0，1}，{A0，A0A}，A)。⑶({A，B}，{0，1}，{A01，A0A1，A1A0，BAB，B0}，A)。⑷({A，B}，{0，1}，{A0，A1，A0A，A1A}，A)。2021/8/8162.2形式定义⑸({S，A，B，C，D},{a，b，c，d,#}，{SABCD，Sabc#，AaaA，ABaabbB，BCbbccC，cCcccC，CDccd#，CDd#，CD#d}，S)。⑹({S},{a，b}，{S00S，S