2. 计算机
  3. 在形式语言中，若文法G的产生式集P为： (1)Z→Bc(2)Z→Zc(3)B→Ab(4)B→Bb(5)A→Aa(6)A→a 则文法G是(27)文法，识别G的自动机为(28)。对于G来说，(29)为文法G可接受的字符串，(30)为文法G不可接受的字符串。 供

在形式语言中，若文法G的产生式集P为： (1)Z→Bc(2)Z→Zc(3)B→Ab(4)B→Bb(5)A→Aa(6)A→a 则文法G是(27)文法，识别G的自动机为(28)。对于G来说，(29)为文法G可接受的字符串，(30)为文法G不可接受的字符串。 供

admin2009-02-15  59
问题 在形式语言中，若文法G的产生式集P为：
(1)Z→Bc(2)Z→Zc(3)B→Ab(4)B→Bb(5)A→Aa(6)A→a
则文法G是(27)文法，识别G的自动机为(28)。对于G来说，(29)为文法G可接受的字符串，(30)为文法G不可接受的字符串。
供选择的答案：
选项 A、abbbcc
B、abcabc
C、aaabcc
D、aabbccc
答案B
解析 形式语言首先于1956年由Chomsky进行描述。该理论讨论了语言与文法的数学理论，按照对文法规则的不同定义形式，对语言和文法进行了分类。一般来说， Chomsky文法是一个四元组G=(VN，Vr，P，Z)，其中VN为非终结符集合，Vr为由终结符组成的字母表集合，P是有穷非空的重写规则集合，Z是识别符号。文法G对应的语言是能从该文法的识别符号产生的那些终结符号串(句子)织成的集合。简单来说，对于文法的分类分为4类：
0型文法也称短语结构文法可以由图灵机识别。
1型文法也称上下文有关文法，可以由线性界限自动机识别。
2型文法也称上下文无关文法，可以由下谁自动机识别。
3型文法也称正则文法可以由有穷状态自动机识别。
具体的文法定义可以参照编译原理中的相关概念。
(29)选项C中，aaabc=Aaabc=Aabc=Abc=Bc=Z语句aaabc经过转换最终到达终结符Z，则aaabc可以被该文法接受；进行归纳；选项B中，aacbb= Aacbb=Acbb  由于Ac在文法集中没有对应的重写规则所以不能被该文法接受，选项A，D同理
(30)选项  B中abcabc=Abcabc=Bcabc=Zabc由于Za在文法集中没有对应的重写规则所以不能被该文法接受，同样的，A中abbbcc=Abbbcc= Bbbcc=Bbcc=Bcc=Zc=Z语句abbcc经过转换最终到达终结符Z，则abbbcc可以被该文法接受 C，D同理
转载请注明原文地址:https://kaotiyun.com/show/CELZ777K
本试题收录于： 系统分析师上午综合知识考试题库软考高级分类
0

系统分析师上午综合知识考试

软考高级

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