Search code examples
automatadfanfa

Trying to draw a Non- Deterministic Finite Automata

I'm completely new to finite automata and kind of struggling to understand the topic.

I'm able to draw simple ones but I have a practice question that asks to:

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.

How do I do this?

Solution

  • Here is a minimal DFA for the language (minimal DFAs are DFAs are NFAs):

                  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 |   |
     \_/        \_/        \_/

    The idea is that state (x,y) is visited after seeing x zeroes and y ones; if you've seen two zeroes and you see another, the string is rejected by transitioning to a dead state; if you've seen two ones, you can see as many more as you like. States of the form (x,2) are accepting.