CHALLENGE: Implement a DFA

[MMcCarthy]

This challenge has been inspired by this question which can be found in the C++ forum.

This challenge however is non language specific.

How to implement a DFA ?

[SammyB]

I need help already: Wikipedia says DFA is a common abbreviation which may refer to any of the following topics [obvious off topic ones are deleted]:
In computing:

• Data flow analysis
• Deterministic finite automaton
• Dual Factor Authentication
• Design for All (DfA)

In science:

• Descent from antiquity
• Direct fluorescent antibody, a medical test
• Detrended fluctuation analysis

In finance:

• Dimensional Fund Advisors
• Dynamic Financial Analysis

In gaming:

• Death From Above (BattleTech), a jump-jet attack tactic in the BattleTech game universe.

In Statistics:

• Discriminant Function Analysis
• Detrended Fluctuation Analysis

In Other Fields:

• Design for Assembly in engineering
• Differential Fault Analysis in security
• Daily Female Appreciation

So, which is it? I vote for Daily Female Appreciation, but that may be too difficult!

[MMcCarthy]

The general consensus is that this stands for:

Deterministic Finite Automaton

[nkg]

DFA Implementation:-
A DFA can be thought of as a tape which reads one character at a time until end of the tape. Each position on a tape puts DFA in a different state.

Lets consider a simple DFA for parsing a string with even number of 'a's and 'b's in a given word of a grammar.

L = {a,b}
Q={S0,S1,S2,S3)
E={abba, aabb, aaaabb, babaaabb....}

Attached is the state transition diagram for above DFA. Start from state 'S0' and take any input from the grammar. If the automata ends at state 'S0', then the given word is valid for grammar, else invalid input.

I hope from the diagram it is easy to write any simple language steps to implement.
[IMG]C:\Documents and Settings\winxpuser\Desktop\DFA.JPG[/IMG]

[r035198x]

Jos' compiler series available through this index page deals with all the components required here. The tokenizing and parsing parts are most relevant.
The general idea here is to determine the conformance of some input to some well defined language/state. That is part of the job of a compiler.

[hdanw]

Been there, done that.

Also : Discrete Finite Automaton.


The quickest and most straight forward method is to build a 2D array of function pointers.

When you get an event that changes state, you update the current state funtion Pointer to the function indexed by the 2d array.

This is very quick, and works well with windows.

IE : the rows would be one for each state, the columns then are one for each event. The data at that coordinate is the state you change to upon the event.

in your update or message loop you set the function executed to manage that state for each cycle.

FunctionPointerCurrentState();
...
on event
{
FunctionPointerCurrentState = 2dStateTransitionTable[CurrentState][CurrentEvent];
}

I have working code, It Hauls balls, and is ideal for game development, or any other real time applications.

Dan -