Search code examples
dfadeterministic

Deterministic Finite State Automaton (DFA) Exam Q

The question is:

Design a Deterministic Finite State Automaton (DFA) according to the following specification:

 Its alphabet is {0, 1}.

 Its language consists of all words with an odd number of 1s.

 0s will not be accepted (even if they are part of the alphabet).

So by this i'm sure it means it'll only accept for example "111" and reject "11"

My first attempt, although it worked (accepts 111 rejects 11) it is accepting 0's enter image description here

My second attempt i tried to create a transition table first then the diagram, but q1 had no stage to q2 unless i did my table incorrectly enter image description here

My final attempt it..worked i think? But i'm not sure if this diagram is valid enter image description here

Could someone give me some insight on which of the 3 diagrams is correct/heading the correct way and how exactly would i solve this/do a transition table

Update: Do you mean like this @Pavel Pája Halbich enter image description here

Solution

  • Your final diagram is good (but not valid). To get it valid, you need to add transitions:

    • q1 -> q2 using 0
    • q2 -> q2 using 0,1 (this is classic fail state)

    Then you will have 3 states and for each state defined transition to other state, one starting state (q0) and a set of accepting states ({q1}).