Deterministic Finite Automata on JFLAP

167 views Asked by At

I have a DFA problem and I need to use JFLAP to create a diagram for the automata. I have successfully done a more simple problem, however I just can't figure out how to solve this one:

"A DFA that receives sequences of "1" and "2" values, accepting only sequences that result in 4. Any other combinations that result in more than or less than 4 are to be rejected."

The alphabet is {1,2} and as far as I know these are the possible combinations that will be accepted:

1111, 22, 121, 112, 211

Any help will be very much appreciated. Thank you.

1

There are 1 answers

0
Patrick87 On

A DFA for this finite language could look a lot like this:

         1       1        1         1
----->q----->q1----->q11----->q111----->q1111
      |       |        |      |         | 
      | 2     | 2      | 1    | 2       | 1,2
      |       |        |      |         |
      V   1   V    1   V      |         |
      q2----->q21----->q211   |         |
      |       |        |      |         |
      | 2     | 2      | 1,2  |         |
      |       |        |      |         |
      V       |        |      |         |
      q22     |        |      |         |
      |       |        |      |         |
      | 1,2   |        |      |         |             +-----+
      |       |        |      |         |             |     | 1,2
      V       V        V      V         V             V     |
      +-------+--------+------+---------+--------->qDead----+

Another approach would be just to remember the current sum:

           1
 ----->q0----->q1
       |       /|
       |      / |
       |     /  |
     2 |  1 /   | 2
       |   /    |
       |  /     |
       | /      |
       |/       |
       V   1    V
       q2----->q3
       |       /|
       |      / |
       |     /  |
     2 |  1 /   | 2
       |   /    |
       |  /     |
       | /      |
       |/       |
       V  1,2   V
       q4----->qDead