尝试绘制非确定性有限自动机

Question

我对有限自动机完全陌生，有点难以理解这个主题。

我能画出简单的，但我有一道练习题要求：

Design a Non- Deterministic Finite Automata that accepts ∑={0,1}. The Non-Deterministic Finite Automata should be able to determine all strings that have at most two zeroes and at least two ones.

我该怎么做？

Answer 1

这是该语言的最小 DFA（最小 DFA 是 DFA 是 NFA）：

              0         0          0
----->(0,0)----->(1,0)----->(2,0)-------+
        |          |          |         |
        | 1        | 1        | 1       |  __
        |          |          |         | /  \
        V    0     V    0     V    0    V V   | 0, 1
      (0,1)----->(1,1)----->(2,1)----->dead--/   
        |          |          |         ^
        | 1        | 1        | 1       |
        |          |          |         |
        V    0     V    0     V    0    |
      (0,2)----->(1,2)----->(2,2)-------+
     /  ^       /  ^       /  ^
  1 |   |    1 |   |    1 |   |
     \_/        \_/        \_/

想法是在看到 x 个零和 y 个之后访问状态 (x,y)；如果您已经看到两个零并且看到另一个零，则该字符串会通过转换为死状态而被拒绝；如果你看过两个，你可以想看多少就看多少。 (x,2) 形式的州正在接受。

尝试绘制非确定性有限自动机

Trying to draw a Non- Deterministic Finite Automata

automata

dfa

nfa