问题 单项选择题

文法G=(VT,VN,P,S)的类型由G中的 (1) 决定。若GO=(a,b,S,X, Y,P,S),P中的产生式及其序号如下:

1:S→XaaY

2:X→YY|b

3:Y→XbX|a

则GO为 (2) 型文法,对应于 (3) ,由GO推导出句子aaaa和baabbb时,所用产生式序号组成的序列分别为 (4) (5)

5()

A.13133

B.12312

C.12322

D.12333

答案

参考答案:C

解析:

文法G是一个四元组

G={VT,VN,S,P}

其中VT是一个非空有限的符号集合,它的每个元素成为终结符号。VN也是一个非空有限的符号集合,它的每个元素称为非终结符号,并且有VT∩VN=Φ。S∈VN,称为文法G的开始符号。P是一个非空有限集合,它的元素称为产生式。所谓产生式,其形式为:α→β。α为产生式的左部,β称为产生式的右部,符号“→”表示“定义为”,并且α、β∈(VT∪VN)*,α≠ε,即α、β是由终结符和非终结符组成的符号串。开始符S必须至少在某一产生式的左部出现一次。另外可以对形如α→β,α→γ的产生式缩写为α→β|γ,以方便书写。

1956年,著名的语言学家Noam Chomsky根据对产生式所施加的限制的不同,把文法分成了四类,并定义了相应的四类形式语言。

0型文法

设G=(VN,VT,P,S),如果它的每个产生式α→β是这样一种结构:α∈(VN∪VT)*且至少含有一个非终结符,而β∈(VN∪VT)*,则G是一个0型文法。0型文法也称短语文法。一个非常重要的理论结果是:0型文法的能力相当于图灵机(Turing)。或者说,任何0型文法语言都是递归可枚举的,反之,递归可枚举集必定是一个0型语言。0型文法是这几类文法中限制最少的一个。

1型文法

1型文法也叫上下文有关文法,此文法对应于线性有界自动机。它是在0型文法的基础上,每一个α→β都有|β|≥|α|。这里的|β|表示β的长度。

注意:虽然要求|β|≥|α|,但有一特例:α→ε地满足1型文法。

如有A->Ba则|β|=2,|α|=1符合1型文法要求。反之,如aA->a,则不符合1型文法。

2型文法

2型文法也叫上下文无关文法,它对应于下推自动机。2型文法是在1型文法的基础上,再满足:每一个α→β有α是非终结符。如A->Ba,符合2型文法要求。

如Ab->Bab虽然符合1型文法要求,但不符合2型文法要求,因为其α=Ab,而 Ab不是一个非终结符。

3型文法

3型文法也叫正则文法,它对应于有限状态自动机。它是在2型文法的基础上满足: A→α|αB(右线性)或A→α|Ba(左线性)。

如有:A->a,A->aB,B->a,B->cB,则符合3型文法的要求。但如果推导为:A->ab, A->aB,B->a,B->cB或推导为:A->a,A->Ba,B->a,B->cB,则不符合3型文法的要求。具体说,例子A->ab,A->aB,B->a,B->cB中的A->ab不符合,如果后面的ab改成一个非终结符就对了。例子A->a,A->Ba,B->a,B->cB中如果把B->cB改为B->Bc就对了,因为A→α|αB(右线性)和A→α|Bα(左线性)两套规则不能同时出现在一个语法中,只能完全满足其中的一个,才能算3型文法。

注意:上面例子中的大写字母表示非终结符,而小写字母表示终结符。

本题中给出的文法、产生式左部均是单个变量,因此是上下文无文法。由此文法推导出句子aaaaa的产生式的序列及推导过程如下:

S→XaaY(使用1式)

→YYaaY(使用2式)

→aYaaY(使用3式)

→aaaaY(使用3式)

→aaaaa(使用3式)

句子baabbb的推导过程为:

S→XaaY(使用1式)

→baaY(使用2式)

→baaXbX(使用3式)

→baabbX(使用2式)

→baabbb(使用2式)

因此产生式序号组成的序列分别是12333和12322。

单项选择题
单项选择题