有限自动机(FA)可用于识别高级语言源程序中的记号(单词),FA可分为确定的有限自动机(DFA)和不确定

Question

有限自动机(FA)可用于识别高级语言源程序中的记号(单词)，FA可分为确定的有限自动机(DFA)和不确定的有限自动机(NFA)。若某DFA D与某NFA M等价，则(48)。

A．DFA D与NFA M的状态数一定相等

B．DFA D与NFA M可识别的记号相同

C．NFA M能识别的正规集是DFA D所识别正规集的真子集

D．DFA D能识别的正规集是NFA M所识别正规集的真子集

Answer 1

正确答案：B
解析：本题考查程序语言翻译基础知识。非确定有限自动机NFA是一个五元组(5-tuple)：M=(S，∑，move，s0，F)其中，①S是有限个状态(state)的集合；②∑是有限个输入字符(包括ε)的集合：③move是一个状态转移函数，move(si，ch)=sj表示，当前状态si下若遇到输入字符ch，则转移到状态即④sj；④s0是唯一的初态(也称开始状态)；⑤F是终态集(也称接受状态集)，它是S的子集，包含了所有的终态。确定的有限自动机DFA是WA的特例：①DFA没有状态具有ε状态转移(ε-transition)，即状态转换图中没有标记ε的边；②对每一个状态s和每一个字符a，最多有一个下一状态。若两个FA识别同一个正规集，则这两个FA等价。对于每个NFA，都存在与之等价的DFA。