问题 单项选择题

在Chomsky定义的4种形式语言文法中,0型文法又称为 (51) 文法;1型文法又称为 (52) 文法;2型语言可由 (53) 识别。

A.图灵机

B.有限自动机

C.下推自动机

D.无限自动机

答案

参考答案:C

解析:[试题51~53分析]
本题考查文法的分类和特点。
Chomsky对文法中的规则施加不同限制,将文法和语言分为4大类:
[*]0型文法(PSG),0型语言或短语结构语言;
[*]1型文法(CSG),1型语言或上下文有关语言;
[*]2型文法(CFG),2型语言或上下文无关语言;
[*]3型文法(RG),3型语言或正则(正规)语言。
由于4种文法是按照将产生式做进一步限制而定义的,所以它们之间是逐级“包含”的关系,由4种文法产生的语言也是逐级“包含”的关系。
由于存在对于某种语言的生成过程,就一定存在对其识别的过程。因此自动机按照其识别能力的大小,可以分为:图灵机、线性有界自动机、下推自动机、有限自动机。与形式文法形成的对应关系分别为:0型文法对应图灵机,1型文法对应线性有界自动机,2型文法对应下推自动机,3型文法对应有限自动机。

单项选择题
单项选择题