Odd Number of Ones
Odd Number of Ones¶
Have you ever left the fridge open? Would it be helpful if the fridge could remind you to close the door if it has been open to long. This is actually a DFA problem.
We have a sensor on the door. We can query the sensor and ask what happened. It we will us either “no change” or “change”. We know for a fact the door starts closed. When the status changes, we can determine the door opened. If it changes again, we know it closed. If we read “no change” then we know that nothing has changed since our last query.
This is a toy example, since a door could easily be hard wired. In a more general sense, we would want to query information from a network or wireless system. So, we need to actually ask for data.
We will need two states even and odd based on the number of changes that have been reported. We also need two symbols. We will use 1 to mean a change and 0 to mean no change.
When the fridge starts, we have an even number of changes. Specifically, we have zero changes since nothing has happened. Zero is an even number. If we query the fridge and there is no change, we stay at even.
When a change happens, we move to the odd state. Again, we can stay here forever with no changes. When we report a change, we move back to even.
The accept state is odd. If we end in the odd state, then we ended with the door open. This is something we could control with a timer.
The DFA would look like the image below.
The source code for the language is given below.
#This DFA Accepts the Language
#L={ Number of 1 chars is odd with sigma={0,1} }
#Define DFA Properties
symbols=(0,1)
states=(even,odd)
start=even
accept=(odd)
#Define Transition Table
if odd and 1 then even
if even and 1 then odd
if odd and 0 then odd
if even and 0 then even