NFA 不接受以“101”结尾的字符串
NFA that does not accept strings ending "101"
不接受以“101”结尾的字符串的 NFA 是什么？
有很多 NFA（实际上是无限多）都有效。这是一个简单的：
/0-\ /1-+--------+--------+
\ | \ | 1 1
\ V \ V | |
----->[q0]--1-->[q1]--0-->[q2]--1-->q3
^ | ^ |
| | | |
\-------------0----/ \--0---/
这个NFA恰好也是一个完全确定性的DFA。没关系。这个 DFA 通过跟踪三个最近遇到的输入符号来工作。如果最近遇到的三个是 000 或 100，机器将以状态 q0 结束。如果最近遇到的三个是 111、011 或 001，则机器将以状态 q1 结束。如果最近遇到的三个是 010 或 110，机器将以状态 q2 结束。如果最近遇到的三个是 101，则机器将在 q3 结束。这些是看到的最后三个符号的所有可能性，并且每个符号都根据语言定义正确地使机器处于接受或不接受状态。
不接受以“101”结尾的字符串的 NFA 是什么？
有很多 NFA（实际上是无限多）都有效。这是一个简单的：
/0-\ /1-+--------+--------+
\ | \ | 1 1
\ V \ V | |
----->[q0]--1-->[q1]--0-->[q2]--1-->q3
^ | ^ |
| | | |
\-------------0----/ \--0---/
这个NFA恰好也是一个完全确定性的DFA。没关系。这个 DFA 通过跟踪三个最近遇到的输入符号来工作。如果最近遇到的三个是 000 或 100，机器将以状态 q0 结束。如果最近遇到的三个是 111、011 或 001，则机器将以状态 q1 结束。如果最近遇到的三个是 010 或 110，机器将以状态 q2 结束。如果最近遇到的三个是 101，则机器将在 q3 结束。这些是看到的最后三个符号的所有可能性，并且每个符号都根据语言定义正确地使机器处于接受或不接受状态。