Arnab Chakraborty's DFA tutorial: page 12 of 11

www.angelfire.com/dragon/letstry
cwave04 at yahoo dot com

My Guestbook

Home >

... tutorials >

... ... DFA

Some more examples

Double click

This example is motivated partly by the double-click mechanism of a mouse, and partly by the keypad of a mobile phone. The problem is this: we have to make a device with a single button and two LEDs such that if we press the button then LED 1 will glow untikl we release the button. If, however, we "double click", (i.e., press-release-press with the time gap between the two presses below a certain threshold) then LED 2 (and not LED 1) will glow. The LED will go off when we release the button.

We shall first design the DFA. Notice that we need to have a timer to measure the time gap between two successive presses. The timer can be in one of two states: on or off. Also the button can be in one of two states: up or down. Combining these possibilities we have 4 states in all:

A little trial-and-error now yields the following state diagram. Here the output S stands for turning LED 1 on, D for LED 2, and Z for turning both LEDs off. Also, the outputs "on" and "off" stands for turning the timer on and off.

Here is the XML representation.


<DFA start="UP_OFF">
  <STATE name="UP_OFF">
    <ON event="PRESS" next="DOWN_ON">
      <T_ON time="5"/>
      printf("\tLED 1 glows\n");
      delay();
    </ON>
  </STATE>

  <STATE name="DOWN_OFF">
    <ON event="RELEASE" next="UP_OFF">
      printf("\tBoth LEDs off\n");
    </ON>
  </STATE>

  <STATE name="UP_ON">
    <ON event="PRESS" next="DOWN_OFF">
      <T_OFF/>
      printf("\tLED 2 glows\n");
      delay();
    </ON>
    <ONTIMEOUT next="UP_OFF"/>
  </STATE>

  <STATE name="DOWN_ON">
    <ON event="RELEASE" next="UP_ON">
      printf("\tBoth LEDs off\n");
    </ON>
    <ONTIMEOUT next="DOWN_OFF"/>
  </STATE>
</DFA>

Mobile keypad unlock

Most mobile phones feature a keypad locking facility that automatically locks the keypad if it lies idle for a spefic amount of time. The typical unlocking technique is to press two particular keys (A and B, say) in rapid succession. If any key other than A is pressed a message like "Press A and then B" is displayed. After A is pressed the message "Press B now" is displayed for some time. If the user fails to press B during this display, the screen reverts to the blank display. If the use presses B before the display vanishes, the keypad is unlocked, and the message "Keypad unlocked" is displayed.

We want to write a microcontroller program that emulates this feature. Specifically, we shall have three buttons A,B and C (the last one representing the rest of the keypad). We start by constructing a DFA.

First consider only the buttons A and B. We shall denote by Ad the pressing of button A, while Au is for releasing it. Similarly for Bd, Bu. Ignore the timing issue. Then we have the state transitions:

Notice that in this first version we have not cared about the release of button A before pressing B. In my mobile, however, this does matter. You must release A before pressing B. So we update the diagram to the following.

Now we bring the time consideration. Each arrow is like a time point. The red arrow must occur within a specified time gap after the green arrow. This means we have to start the timer in the green arrow, and turn it off in the red arrow. Also, we have to worry about what happens if the timer expires before reaching the red arrow. Well, we shall keep it simple by assuming that all time outs lead to the initial locked state.

Next the C button enters into picture. Since C does not play any role in the unlocking algoithm, any occurence of the inputs Cd or Cu takes us to the locked state. We shall not clutter our diagram by explicitly showing this. Finally, we shall introduce the messages. We shall have three LEDs L, P and U corresponding to the messages: "Press A and then B", "Press B now" and "Keypad is unlocked". Some of the outputs are trivial to insert in the transition diagram.

The tricky LED is L. we need to display it for some time whenever the unlocking algorithm is not followed properly. So we shall split the "locked" state into two: "locked with message" and "locked without message".

We can of course add further details like clearing the "Unlocked" message after a delay, etc. But all those embellishments are routine, and are best left as exercises.

hit counter