Arnab Chakraborty's DFA tutorial: page 11 of 11

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

My Guestbook

Home >

... tutorials >

... ... DFA

Implementing a continuous time DFA

At the end of the last page we had the following DFA.

We shall now discuss three ways to implement this in C. The first method will be a brute-force method that would become rather confusing for a more elaborate DFA. The second method is more structured and elegant.

The brute-force method

Notice that each self-loop is basically a for- or while-loop to wait for something to occur. So we can use the following code:

unsigned int dfa_time, dfa_timeout; unsigned char dfa_timerRunning = 0, dfa_state = DIGIT;	1
while(1) { if(dfa_timerRunning) dfa_time++;	2
switch(dfa_state) { case DIGIT: if(STD==1) { doX(); dfa_state = NODIGIT; break; } if(dfa_time>=dfa_timeout) { dfa_time = 0; dfa_timerRunning = 0; doY(); dfa_state = DIGIT; break; } break; case NODIGIT: if(STD==0) { dfa_state = DIGIT; dfa_time = 0; dfa_timeout = 4; dfa_timerRunning = 1; break; } break; }	3
}

Explanation of the code:

1:: We need some variables for the DFA. These all have names starting with dfa_.
2:: The entire DFA is inside a big while-loop. The first thing that we do in each pass through this loop is to increment the time counter if the timer is running. In this simple code we are not caring about "roll over"s.
3:: The switch-statement is the heart of the DFA. Here we make decisions based on the current state.

This DFA is not very complicated. But still the C code is not too transparent. Do not blame yourself (or me, either, for that matter) if it looks complex. However, there is a sort of structure in the code inside the switch-statement that is worth exploring.

The code for a a typical state like this one

has a generic format:


case S:
   if(condition 1) {
     Take action 1;
     state = S₁;
     break;
   }
     .
     .
     .
   if(condition k) {
     Take action k;
     state = S_k;
     break;
   }

   if(dfa_time>=dfa_timer) {
     Take "time out" action;
     state = T;
     break;
   }

   break;

This gives us an idea for writing structured code for continuous time DFA's.

Structured implementation of continuous time DFA's

The idea is to come up with a coding scheme that is as close as possible to the DFA transition diagram. All routine implementational details should be hidden. XML is emminently suited for this purpose. The following XML code, for example, specifies our DFA.

<DFA start="DIGIT">	0
<STATE name="DIGIT">	1
<ON event="STD==1" next="NODIGIT">	2
<T_OFF/>	3
doX();	4
</ON>
<ONTIMEOUT next="DIGIT">	5
doY();	6
</ONTIMEOUT> </STATE> <STATE name="NODIGIT"> <ON event="STD==0" next="DIGIT">
<T_ON time="4"/>	7
</ON> </STATE> </DFA>

Explanation of the code:

0:: The entire specification is within the <DFA> tag. The initial state is given as the start attribute.
1:: Each state is inside its own <STATE> tag. We can refer to it later using its name.
2:: Each <ON> specifies an input. The event is any boolean C-expression. The next state is also specified as an attribute.
3:: <T_OFF> turns the timer off.
4:: Here we can put as many lines of C code as we want. These lines constitute the output for this state transition.
5:: <ONTIMEOUT> is the special input corresponding to expiration of the timer. This also stops the timer automatically.
6:: The "time out" action can be any number of lines of C code.
7:: <T_ON> turns the timer on. Its time attribute specifies the lifespan. It must be a strictly positive integer.

A simple stylesheet written in XSL can convert it to C. Here is a complete XML file that contains the above XML code plus some supporting routines etc. And here is a XSL file that translates the XML file to a C program. (These links lead to htmlified versions of the xml and xsl files, because some browsers like mozilla have problem displaying raw xml and xsl files). There are various ways of "applying" the XSL file on the XML file. The simplest is just view the raw XML file using a browser (almost any reasonable browser would do, Konqueror not counting as one). For example just click on this link to the raw XML file. You'll directly see the C program generated by your browser on the fly. The XSL file is already linked from the XML file (that is why your browser can generate the C program automatically).

hit counter