不确定有穷自动机NFA

有穷自动机

本质上与状态转换图相同，但有穷自动机只回答Yes/No

分为两类：

• 不确定的有穷自动机（NFA）：边上的记号没有限制，一个符号可以出现在离开同一个状态的多条边上，空串可以做标号。

• 确定的有穷自动机（DFA）：对于每个状态以及每个符号，有且只有一条边（或最多只有一条边）

两种自动机都识别正则语言，对于每个可以用正则表达式描述的语言，均可用某个NFA或DFA来识别。

识别：判别一个串是否属于对应正则语言（Yes/No）

NFA的定义（五元组）

转换表表示法

用二维表表示NFA的转换函数：

• 每行对应一个状态

• 每列对应于一个输入符号或者空串

• 每个条目表示对应的后继状态集合

输入字符串的接受

NFA接受的语言：从开始状态到达接受状态的所有可能路径的标号串的集合，即该NFA接受的所有符号串的集合。