计算(jìsuàn)理论去某范式第2章上下文无关(wúguān)文法上下文无关(wúguān)文法的引入对任何语言L，有一个字母表∑，使得L∑*。L的具体组成结构是什么样的？一个给定的字符串是否为一个给定语言的句子?如果不是，它在结构的什么地方出了错？进一步地，这个错误是什么样的错？如何更正？……。这些问题对有穷语言来说，比较容易解决。这些问题对无穷语言来说，不太容易解决。用文法作为相应语言的有穷描述不仅可以描述出语言的结构特征，而且(érqiě)还可以产生这个语言的所有句子例：1）哈尔滨是美丽的城市2）北京是祖国的首都(shǒudū)3）集合是数学的基础4）形式语言是很抽象的4个句子的主体结构<名词短语><动词短语><句号><名词短语>={哈尔滨，北京，集合，形式语言}<动词短语>={是美丽的城市，是祖国的首都(shǒudū)，是数学的基础，是很抽象的}<句号>={。}<动词短语>可以是<动词><形容词短语>或者(huòzhě)<动词><名词短语>。<名词短语>={北京、哈尔滨、形式语言、集合、美丽的城市、祖国的首都、数学的基础}。<动词>={是}。<形容词短语>={很抽象的}。把<名词短语><动词短语><句号>取名为<句子>。表示成αβ形式<句子><名词短语><动词(dòngcí)短语><句号><动词(dòngcí)短语><动词(dòngcí)><形容词短语><动词(dòngcí)短语><动词(dòngcí)><名词短语><动词(dòngcí)>是表示一个语言(yǔyán)，需要4种东西⑴形如<名词短语>的“符号”它们表示相应语言(yǔyán)结构中某个位置上可以出现的一些内容。每个“符号”对应的是一个集合，在该语言(yǔyán)的一个具体句子中，句子的这个位置上能且仅能出现相应集合中的某个元素。所以，这种“符号”代表的是一个语法范畴。⑵<句子>所有的“规则”，都是为了说明<句子>的结构而存在，相当于说，定义的就是<句子>。⑶形如北京的“符号”它们是所定义语言的合法句子(jùzi)中将出现的“符号”。仅仅表示自身，称为终极符号。⑷所有的“规则”都呈αβ的形式在产生语言的句子(jùzi)中被使用，称这些“规则”为产生式。文法的形式(xíngshì)定义文法的形式(xíngshì)定义文法(wénfǎ)例1约定(yuēdìng)⑵使用符号英文字母表较为前面的大写字母，如A，B，C，…表示语法变量(biànliàng)；英文字母表较为前面的小写字母，如a，b，c，…表示终极符号；希腊字母α，β，γ…表示由语法变量(biànliàng)和终极符号组成的行推导(tuīdǎo)(derivation)定义(dìngyì)定义(dìngyì)文法(wénfǎ)的构造例1文法(wénfǎ)的构造例2文法(wénfǎ)的构造例3文法(wénfǎ)的乔姆斯基体系文法(wénfǎ)的乔姆斯基体系文法(wénfǎ)的乔姆斯基体系文法(wénfǎ)的乔姆斯基体系文法(wénfǎ)的乔姆斯基体系文法(wénfǎ)的乔姆斯基体系定理(dìnglǐ)2.1上下文无关文法(wénfǎ)概述上下文无关文法(wénfǎ)示例上下文无关(wúguān)文法示例上下文无关(wúguān)文法的形式化定义上下文无关文法(wénfǎ)举例乔姆斯基范式(fànshì)ChomskyNormalForm乔姆斯基范式(fànshì)ChomskyNormalForm例例先引入变量(biànliàng)Ba，Bb和产生式Baa，Bbb，完成第一步变换。SBbA|BaBABbAA|BaS|aBBaBB|BbS|bBaaBbb引入新变量(biànliàng)B1、B2SBbA|BaBABbB1|BaS|aBBaB2|BbS|bBaaBbbB1AAB2BB不能因为原来有产生(chǎnshēng)式Aa和Bb而放弃引进变量Ba、Bb和产生(chǎnshēng)式Baa、Bbb。L(A)={x|x∈{a，b}+&x中a的个数比b的个数恰多1个}。L(B)={x|x∈{a，b}+&x中b的个数比a的个数恰多1个}。L(Ba)={a}。L(Bb)={b}。习题(xítí)2.2下推自动机PushdownAutomata有穷自动机的物理(wùlǐ)模型PDA的物理(wùlǐ)模型例例PDA的形式化描述(miáoshù)PDA的基本(jīběn)结构下推自动机M被定义为6元组(Q，，，，q0，F)，这里Q，，和F都是有穷集合，并且：Q是状态集是输入字母表栈字符表q0Q是起始状态FQ是接受状态集是状态转移函数