单选题
已知文法G1=(VT=a,b,d,VN=S,A,B,S,P),其中P为:
S→dAB
A→aA|a
B→bB|ε
该文法属于 (28) 文法。
【正确答案】
C
【答案解析】[解析] 乔姆斯基(Chomsky)把文法分成4种类型,即0型、1型、2型和3型,由此产生的语言分别称为0型、1型、2型和3型语言。这几类文法的差别在于对产生式的形式施加不同的限制,如下表所示。
[*]
0型文法也称短语文法,1型文法也称上下文有关文法,2型文法也称上下文无关文法, 2型文法的识别器模型是下推自动机。3型文法也称线性文法(或称正规文法),其识别器模型是有限状态自动机。
文法G1的所有产生式形式都是A→β,其中A∈VN,β∈V*,且第1条规则S→dAB是非线性的,因此文法G1属于2型文法,又称上下文无关文法。