Skip to content
Matthias Klatte edited this page Nov 23, 2014 · 4 revisions

Deterministic finite automaton (wikipedia)

File: DFA.Script.txt

Usage

In the following I will use this example graph:
http://upload.wikimedia.org/wikipedia/commons/thumb/9/9d/DFAexample.svg/250px-DFAexample.svg.png

1. Create a new Instance

declare myDFA = DFA_Create();

2. Add States

declare s1 = DFA_AddState(myDFA);
declare s2 = DFA_AddState(myDFA);

Note that you can give a custom name to your state using DFA_AddState(myDFA, "State1") which can be useful for debugging.

3. Define the input alphabet

You might want to define everything as variable for later use, so you could have

declare ie = "EPSILON";
declare i0 = "0";
declare i1 = "1";
DFA_AddToAlphabet(myDFA, ie);
DFA_AddToAlphabet(myDFA, i0);
DFA_AddToAlphabet(myDFA, i1);

EPSILON is a special symbol allowing every input.

4. Define transition rules

Rules are defined as DFA_DefineRule(_Instance, _FomState, _Input, _ToState). In the example that would be

DFA_DefineRule(myDFA, s1, i0, s2);
DFA_DefineRule(myDFA, s1, i1, s1);

DFA_DefineRule(myDFA, s2, i0, s1);
DFA_DefineRule(myDFA, s2, i1, s2);

5. Define Accepting States and Starting State

DFA_AddAcceptingState(myDFA, s1);

DFA_SetStart(myDFA, s1);

6. Validating an Input Sequence

Now that the automaton is set up, we can test it with a sequence of inputs. Since the whole thing is based on strings and we have the possibility to use longer inputs for transitions, we have to validate an array of strings.

declare Boolean matches;
matches = DFA_Evaluate(myDFA, [i0, i0, i1]); // True
matches = DFA_Evaluate(myDFA, [i1, i1, i0]); // False

With DFA_GetCurrentState() we could now return us the state, the automaton stopped the execution.

Logging

You can set the logging level with the variable DFA_LogLevel which will affect all following DFA_* functions. Available LogLevel values are

  • DFA_LOGLEVEL_NONE
  • DFA_LOGLEVEL_ERROR (Default)
  • DFA_LOGLEVEL_WARN
  • DFA_LOGLEVEL_DEBUG

Tools

Aside from the methods mentioned in the example above, you can use the following functions to get the DFA status when constructing it:

  • Boolean DFA_StateExists(_Instance, _State, (Boolean) _Logging)

  • Text[] DFA_GetStates(_Instance)

  • Text[] DFA_GetAcceptingStates(_Instance)

  • Text DFA_GetStart(_Instance)

  • Integer DFA_GetStatesCount(_Instance)

  • Text[] DFA_GetAlphabet(_Instance)

  • Void DFA_RemoveFromAlphabet(_Instance, _Input)

  • Void DFA_RemoveAcceptingState(_Instance, _State)

You can’t perform that action at this time.