非确定有限自动机NFA的确定化 |
| |
作者姓名: | 索红军 |
| |
作者单位: | 陕西渭南师范学院计算机科学系 |
| |
摘 要: | 在编译系统中,词法分析阶段是整个编译系统的基础。对于单词的识别,有限自动机FA是一种十分有效的工具。有限自动机由其映射f是否为单值而分为确定的有限自动机DFA和非确定的有限自动机NFA。在非确定的有限自动机NFA中,由于某些状态的转移需从若干个可能的后续状态中进行选择,故一个NFA对符号串的识别就必然是一个试探的过程。这种不确定性给识别过程带来的反复,无疑会影响到FA的工作效率。因此,对于一个非确定的有限自动机NFA M,经常的做法是构造一个确定的有限自动机DFA M’。
|
关 键 词: | 有限自动机 编译系统 词法分析 不确定性 工作效率 DFA 识别 符号串 状态 单值 |
本文献已被 CNKI 维普 等数据库收录! |
|