问题
单项选择题
已知文法G1=(VT=a,b,d,VN=S,A,B,S,P),其中P为:
S→dAB
A→aA|a
B→bB|ε
该文法属于()文法。
A.0型
B.上下文有关
C.上下文无关
D.正规
答案
参考答案: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型文法,又称上下文无关文法。