一.单选题
1.不是DFA的构成成分的是:
- A、有穷字母表
- B、初始状态集合
- C、终止状态集合
- D、有限状态集合
正确答案： B
根据DFA的定义可知,DFA只能有唯一确定的起始状态。
2.下面关于DFA说法正确的是:
- A、一个DFA,可以通过多条路径识别一个符 串
- B、一个DFA识别的语言是一个无限集合,则该DFA的状态数也得是无限个
- C、一个DFA识别的语言是一个无限集合,则该DFA的状态图一定含有回路
- D、一个DFA无法接受空串ε
正确答案： C
A中DFA每个状态的后续状态都是确定的,它对每个符 串的识别路径也是确定的,只有一条识别路径;B中根据概念所知,DFA的状态数都是有限个;D中只要DFA开始状态也是终止状态,则该DFA就能识别空串。
3.有限自动机M和N等价是指:
- A、M和N的字母表相同
- B、M和N状态数相等
- C、M和N状态数或有向边数相等
- D、M和N识别的字符串集合相同
正确答案： D
自动机的实现通常有两种方法:状态转换矩阵法和直接转向法。状态转换矩阵法优点是程序短,但占用存储空间多;直接转向法是基于状态转换图的方法,优点是占用空间小,但程序较长。
二.多选题
1.自动机实现的直接转向法说法正确的是:
- A、直接转向法是基于状态转换图实现的一种方法
- B、直接转向法程序设计简单,但占用存储空间大
- C、直接转向法是基于状态转换矩阵实现的一种方法
- D、直接转向法占用存储空间小,但相应的程序较长
正确答案： AD
三.简答题
1.设计确定有限状态自动机，识别被5整除的二进制正整数（不包括有前导零的数）。
参考答案：
PS:
声明：本站部分文章及图片源自用户投稿，如本站任何资料有侵权请您尽早请联系jinwei@zod.com.cn进行处理,非常感谢！