有限自动机M和N等价是指()。A.M和N的字母表相同B.M和N的状态数和有向边数相等C.M和N状态数或有向边数相等D.M和N识别的字符串集合相同
有限自动机M和N等价是指()。
A.M和N的字母表相同
B.M和N的状态数和有向边数相等
C.M和N状态数或有向边数相等
D.M和N识别的字符串集合相同
参考答案和解析
D 根据等价概念。
相关考题:
●根据乔姆斯基于20世纪50年代建立的形式语言的理论体系,语言的文法被分为4种类型,即0型(短语文法),1型(上下有关文法)、2型(上下文无关文法)和3型(正规文法)。其中,2型文法与 (28) 等价,所以有足够的能力描述多数现今程序设计的语言的句法结构。一个非确定的有限自动机必存在一个与之等价 (29) 。从文法描述语言的能力来说, (30) 最强, (31) 最弱,由4类文法的定义可知: (32) 必是2型文法。(28) A.线性有限自动机B.非确定的下推自动机C.图灵机D.有限自动机(29) A.确定的有限自动机B.图灵机C.非确定的下推自动机D.非确定的有限自动机(30) A.1型文法B.2型文法C.3型文法D.0型文法(31) A.3型文法B.2型文法C.0型文法D.1型文法(32) A.1型文法B.0型文法C.3型文法D.2型文法
有限状态自动机可用五元组(∑,Q,δ,q0,Qf)来描述,设有一个有限状态自动机M的定义如下:∑={0,1},Q={q0,q1,q2},Qf={q2},δ定义为:δ(q0,0)=q1,δ(q1,0)=q2,6(q2,0)=q2,δ(q2,1)=q2。M是一个(28)有限状态自动机,所表示的语言陈述为(29)。(51)A.歧义B.非歧义C.确定的D.非确定的
下图所示为两个有限自动机M1和M2(A是初态、C是终态),(48)。A.M1和M2都是确定的有限自动机B.M1和M2都是不确定的有限自动机C.M1是确定的有限自动机,M2是不确定的有限自动机D.M1是不确定的有限自动机,M2是确定的有限自动机
下图是一有限自动机的状态转换图,该自动机所识别语言的特点是(45),等价的正规式为(46)。A.由符号a、b构成且包含偶数个a的串B.由符号a、b构成且开头和结尾符号都为a的串C.由符号a、b构成的任意串D.由符号a、b构成且b的前后必须为a的串
根据乔姆斯基20世纪50年代建立的形式语言的理论体系,语言的文法被分为四种类型,即:O型(上下文有关文法)、1型(上下文相关文法)、2型(上下文无关文法)和3型(正规文法)。其中2型文法与(66)等价,所以有足够的能力描述多数现今程序设计的语言的句法结构。一个非确定的有限自动机必存在一个与之等价(67)。从文法描述语言的能力来说,(68)最强,(69)最弱,由四类文法的定义可知:(70)必是2型文法。(40)A.确定的有限自动机B.图灵机C.非确定的下推自动机D.非确定的有限自动机E.有限自动机
● 有限自动机(FA)可用于识别高级语言源程序中的记号(单词),FA 可分为确定的有限自动机(DFA)和不确定的有限自动机(NFA)。若某DFA D 与某NFA M等价,则 (48) 。(48)A. DFA D 与NFA M的状态数一定相等B. DFA D 与NFA M可识别的记号相同C. NFA M能识别的正规集是DFA D 所识别正规集的真子集D. DFA D 能识别的正规集是NFA M所识别正规集的真子集
如图3-1所示为一确定有限自动机(DFA)的状态转换图,与该自动机等价的正规表达式是(1),图中的(2)是可以合并的状态。A.(a|b)* bb(a*b*)*B.(a|b)*bba*|b*C.(a*b*)bb(a|b)*D.(a*|b*)*bb(a*|b*)
根据乔姆斯基于20世纪50年代建立的形式语言的理论体系,语言的文法被分为4种类型,即0型(短语文法),1型(上下文有关文法)、2型(上下文无关文法)和3型(正规文法)。其中,2型文法与(28)等价,所以有足够的能力描述多数现今程序设计的语言的句法结构。一个非确定的有限自动机必存在一个与之等价(29)。从文法描述语言的能力来说,(30)最强,(31)最弱,由4类文法的定义可知:(32)必是2型文法。A.线性有限自动机B.非确定的下推自动机C.图灵机D.有限自动机
某一非确定性有限自动机(NFA)的状态转换图如图6-1所示,该NFA等价的正规式是(1),与该NFA等价的DFA是(2)。A.0*|(0|1)0B.(0|10)*C.0*((0|1)0)*D.0*(10)*
某一非确定性有限自动机(NFA)的状态转换图如下图所示,与该NFA等价的正规式是(28),与该NFA等价的DFA是(29)。A.0*|(0|1)0B.(0|10)*C.0*((0|1)0)*D.0*(10)*
某一确定有限自动机(DFA)的状态转换图如下,与该自动机等价的正规表达式是(28),图中(29)是可以合并的状态。(42)A.(a|ba)*bb(a*b*)*B.(a|ba)*bba*|b*C.(a*|b*)bb(a|b)*D.(a|b*)*bb(a*|b*)
● 下图所示为两个有限自动机M1和M2(A是初态、C是终态), (48) 。(48)A. M1和M2都是确定的有限自动机B. M1和M2都是不确定的有限自动机C. M1是确定的有限自动机,M2是不确定的有限自动机D. M1是不确定的有限自动机,M2是确定的有限自动机
图2-7为一确定有限自动机(DFA)的状态转换图,与该自动机等价的正规表达式是(14),图中的(15)是可以合并的状态。A.[a|(ba)]*bb(a*b*)*B.(a|b)*bba*|b*C.(a*b*)bb(a|b)*D.(a|b)*bb(a*|b*)*
如果某个程序的输入数据的可能值划分为n个合理等价类,m个不合理等价类,这些等价类均为数轴上的一个有限区间范围,则采用边缘值测试方法至少需要()A、m+nB、2m+nC、2n+mD、2(m+n)
单选题如果某个程序的输入数据的可能值划分为n个合理等价类,m个不合理等价类,这些等价类均为数轴上的一个有限区间范围,则采用边缘值测试方法至少需要()Am+nB2m+nC2n+mD2(m+n)