根据乔姆斯基于20世纪50年代建立的形式语言的理论体系,文法被分为4种类型,即0型(短语文法)、1型(上下文有关文法)、2型(上下文无关文法)和3型(正规文法)。其中,2型文法与(1)等价,所以有足够的能力描述多数现今程序设计的语言的语法结构。一个非确定的有穷自动机必存在一个与之等价的(2)。从文法描述语言的能力来说,(3)最强,(4)最弱,由4类文法的定义可知(5)必是2型文法。
A.确定的有穷自动机
B.图灵机
C.非确定的下推自动机
D.非确定的有穷自动机
E.有穷自动机
某有限状态自动机的状态图如图2-4所示(状态0是初态,状态2是终态),则该自动机不能识别()。
A、abab
B、aabb
C、bbaa
D、bbab
某一确定有限自动机(DFA)的状态转换图如下图,与该自动机等价的正规表达式是(28),图中(29)是可以合并的状态。
(56)
A.ab*a
B.ablab*a
C.a*b*a
D.aa*lb*a