NFA

Matthias Klatte edited this page Nov 23, 2014 · 1 revision

Nondeterministic finite automaton (wikipedia)

File: NFA.Script.txt

Usage

The following example will match the pattern ab+|aac|aab. For simplicty reasons I use the non-minimized graph as shown: 1. Create a new Instance

declare myNFA = NFA_Create();

declare s  = NFA_AddState(myNFA, "s");
declare q1 = NFA_AddState(myNFA);
declare q2 = NFA_AddState(myNFA);
declare q3 = NFA_AddState(myNFA);
declare q4 = NFA_AddState(myNFA);
declare q5 = NFA_AddState(myNFA);
declare q6 = NFA_AddState(myNFA);
declare q7 = NFA_AddState(myNFA);
declare q8 = NFA_AddState(myNFA);

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

3. Define the used inputs

You might want to define the inputs your automaton uses for later function calls

declare a = "a";
declare b = "b";
declare c = "c";

4. Define transition rules

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

// The ->a->b<-b path
NFA_DefineRule(myNFA, s, a, q1);
NFA_DefineRule(myNFA, q1, b, q2);
NFA_DefineRule(myNFA, q2, b, q2);

// The ->a->a->c path
NFA_DefineRule(myNFA, s, a, q3);
NFA_DefineRule(myNFA, q3, a, q4);
NFA_DefineRule(myNFA, q4, c, q5);

// The ->a->a->b path
NFA_DefineRule(myNFA, s, a, q6);
NFA_DefineRule(myNFA, q6, a, q7);
NFA_DefineRule(myNFA, q7, b, q8);

5. Define Accepting States and Starting State

NFA_SetStart(myNFA, s);

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.

log(NFA_Evaluate(myNFA, [a, a, a]));           // False
log(NFA_Evaluate(myNFA, [a, b]));              // True
log(NFA_Evaluate(myNFA, [a, a, c, b]));        // False
log(NFA_Evaluate(myNFA, [a, a, c, b], False)); // True: The last parameter stops the evaluation when reaching an accepting state
log(_NFA_Remainder);  // [b] This will contain an array of inputs that remain after stoping in an accepting state
log(NFA_Evaluate(myNFA, [a, a, c]));           // True
log(NFA_Evaluate(myNFA, [a, b, b, b]));        // True
log(NFA_Evaluate(myNFA, [a, a, b]));           // True
log(NFA_GetCurrentState(myNFA));               // Will equal variable q8

With NFA_GetCurrentState() we could now return us the state, the automaton stopped the execution. Note that it will be overwritten each evalutation.

Logging

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

• NFA_LOGLEVEL_NONE
• NFA_LOGLEVEL_ERROR (Default)
• NFA_LOGLEVEL_WARN
• NFA_LOGLEVEL_DEBUG
Clone this wiki locally
You can’t perform that action at this time.