Joh*_*ohn 15 grammar chomsky-hierarchy
我正在尝试理解四种不同的乔姆斯基语言类型,但我发现的定义并不对我有任何意义.我知道类型0是自由语法,类型1是上下文敏感,类型2是上下文无关,而类型3是常规.所以,有人可以解释一下并将其置于上下文中,谢谢.
Att*_*ila 24
语言是属于该语言的单词集.但是,很多时候,不是列出语言中的每个单词,而是指定生成语言单词的规则集(并且仅指定那些单词)来识别所讨论的语言是足够的.
注意:可以有多组规则来编写相同的语言.
通常,对规则的限制越多,语言的表达就越少(从规则中生成的单词越少),但如果单词属于规则指定的语言,则更容易识别.由于后者,我们希望识别对其规则具有最多限制的语言,这些语言仍然允许我们生成相同的语言.
关于规则的几句话:一般来说,你描述一个有四个项目的正式语言(AKA是一个四元组):
终端符号(AKA字母)是语言单词组成的符号,通常是小写英文字母的子集(例如'a','b','c')
非终端符号在单词的生成中标记中间状态,指示可能的变换仍然可以应用于中间"单词".终端和非终端符号之间没有重叠(即两个集合的交集是空的).用于非终端的符号通常是大写英文字母的子集(例如'A','B','C')
规则表示对一系列终端和非终端符号的可能转换.它们的形式为:左侧 - >右侧,左侧和右侧均由一系列终端和非终端符号组成.一个示例规则:aBc - > cBa,这意味着在生成单词期间,一系列符号"aBc"(作为中间"单词"的一部分)可以用系列"cBa"替换.
起始符号是专用的非终端符号(通常用S表示),表示单词生成的"根"或"开始",即在单词生成系列中应用的第一个规则始终具有起始符号作为它的左侧.
当所有非终端都被终端替换时,一个字的生成成功结束(因此最终的"中间词"仅由终端符号组成,这表示我们到达了有问题语言的单词).
当并非所有非终端都被终端替换时,单词的生成是不成功的,但是没有可以应用于当前中间"单词"的生产规则.在这种情况下,生成必须遵循生产规则应用程序的不同路径,从起始符号重新划分.
示例:
L = { T,N,P,S},
哪里
T = {a,b,c}
N = {A,B,C,S}
P = {S-> A,S-> AB,S-> BC,A-> a,B-> bb,C-> ccc}
表示三个单词的语言:"a","abb"和"bbccc"
规则的示例应用:
S-> AB-> AB-> ABB
我们1)从起始符号(S)开始,2)应用第二个规则(用AB代替S),3)应用第四个规则(用a代替A)和4)应用第五个规则(用bb代替B) ).由于结果"abb"中没有非终端,因此它是该语言的一个词.
在一般性地讨论规则时,希腊符号alpha,beta,gamma等表示(可能是空的)一系列终端+非终端符号; 希腊字母epsilon表示空字符串(即空符号系列).
乔姆斯基等级中的四种不同类型描述了不同表达能力的语法(对规则的不同限制).
类型0(或无限制)语法生成的语言最具表现力(受限制较少).所述一组递归可枚举语言包含可使用图灵机(基本上是计算机)来生成的语言.这意味着如果你的语言比这种类型更具表现力(例如英语),你就不能编写一种能够列出语言中每一个(也只是这些)单词的算法.规则有一个限制:规则的左侧不能为空(没有符号可以"突然出现").
Type 1(上下文相关)语法生成的语言是上下文相关语言.规则有以下形式的限制:alpha A beta - > alpha gamma beta,其中alpha和beta可以为空,gamma是非空的(例外:S-> epsilon规则,只有在起始符号S不出现在任何规则的右侧).这限制规则在其左侧至少有一个非终端并允许它们具有"上下文":此规则示例中的非终端A可以用伽马替换,只有当它被包围时("是在")alpha和beta的背景下.规则的应用保留了上下文(即alpha和beta不会改变).
Type 2(无上下文)语法生成的语言是无上下文语言.规则的限制是它们的形式为:A - > gamma.这限制了规则在其左侧只有一个非终端并且没有"上下文".这实质上意味着,如果您在中间词中看到非终端符号,则可以应用其左侧具有该非终端符号的任何一个规则,以将其替换为右侧,而不管周围环境如何非终端符号.大多数编程语言都有无上下文生成语法.
所产生的语言3型(普通)语法是普通的语言.规则具有以下形式的限制:A-> a或A-> aB(如果起始符号S没有出现在任何规则的右侧,则允许规则S-> epsilon),这意味着每个非终端必须产生恰好一个终端符号(也可能是一个非终端符号).在正则表达式生成/识别这种类型的语言.
可以以某种方式提升/修改这些限制中的一些以保持修改的语法具有相同的表达能力.修改后的规则可以允许其他算法识别语言的单词.
请注意(如前所述)语言通常可以由多个语法生成(甚至属于不同类型的语法).语言家族的表达能力通常等同于可以生成这些语言的最具限制性语法类型的表达能力(例如,由常规(类型3)语法生成的语言也可以由类型2语法生成,但是它们的表现力功率仍然是3型语法的功能).
例子
在正规文法
T = {a,b}
N = {A,B,S}
P = {S-> aA,A-> aA,A-> aB,B-> bB,B-> b}
生成包含以非零数字'a'开头的单词,然后是非零数字'b'的语言.请注意,不可能描述一种语言,其中每个单词由多个'a'后跟相同数量的'b'和常规语法组成.
无上下文语法
T = {a,b}
N = {A,B,S}
P = {S-> ASB,A-> a,B-> b}
生成一种语言,其中包含以非零数字'a'开头的单词,后跟相同数量的'b'.请注意,不可能描述一种语言,其中每个单词由多个'a'组成,后跟相同数量的'b',后跟相同数量的'c'和无上下文语法.
该上下文有关文法
T = {a,b,c}
N = {A,B,C,H,S}
P = {S-> aBC,S-> aSBC,CB-> HB,HB-> HC,HC-> BC,aB-> ab,bB-> bb,bC-> bc,cC-> cc}
生成一种语言,其中包含以非零数字'a'开头的单词,后跟相同数量的'b',后跟相同数量的'c'.H在这个语法中的作用是能够将CB组合"交换"到BC组合,因此可以在左侧收集B,并且可以在右侧收集C.请注意,不可能描述一种语言,其中单词由一系列'a'组成,其中'a'的数量是具有上下文敏感语法的素数,但是可以编写生成该语言的无限制语法.