2. 计算机
  3. 在Chomsky定义的4种形式语言文法中，0型文法又称为(51)文法；1型文法又称为(52)文法；2型语言可由(53)识别。

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

admin2010-01-17  47
问题 在Chomsky定义的4种形式语言文法中，0型文法又称为(51)文法；1型文法又称为(52)文法；2型语言可由(53)识别。
选项 A、图灵机
B、有限自动机
C、下推自动机
D、无限自动机
答案C
解析 本题考查文法的分类和特点。Chomsky对文法中的规则施加不同限制，将文法和语言分为4大类：
0型文法(PSG)，0型语言或短语结构语言；
1型文法(CSG)，1型语言或上下文有关语言；
2型文法(CFG)，2型语言或上下文无关语言；
3型文法(RG)，3型语言或正则(正规)语言。
由于4种文法是按照将产生式做进一步限制而定义的，所以它们之间是逐级“包含”的关系，由4种文法产生的语言也是逐级“包含”的关系。由于存在对于某种语言的生成过程，就一定存在对其识别的过程。因此自动机按照其识别能力的大小，可以分为：图灵机、线性有界自动机、下推自动机、有限自动机。与形式文法形成的对应关系分别为：0型文法对应图灵机，1型文法对应线性有界自动机，2型文法对应下推自动机，3型文法对应有限自动机。
转载请注明原文地址:https://www.kaotiyun.com/show/UqjZ777K
本试题收录于： 程序员上午基础知识考试题库软考初级分类
0

程序员上午基础知识考试

软考初级

相关试题推荐
随机试题
最新回复(0)