Implementing A Nondeterminisic Finite Automaton(NFA)

Question

I'm trying to a develop a simulation that executes a non deterministic finite automaton in Java. The first command line argument is a text file that defines the machine. The second argument is an input string. If it accepts the string, it prints to standard output "accept" followed by a list of accept states it can end in. If it rejects, it outputs "reject" followed by a list of all possible end states.

For example, the text:

state   1   start
state   2
state   7   accept
transition  1   0   1
transition  1   1   1
transition  1   0   2
transition  2   0   2
transition  2   0   1
transition  2   1   1
transition  2   0   7
transition  7   0   7
transition  7   1   7

which looks like:

with an input string of 10 would output

reject 1 2

and with an input string of 000 would output

accept 7

I need advice on what data structures to use. I thought about using hashmaps and sets but I'm not sure.

Prototherian

How does this machine decide when to transition to another state? – Copra

@Copra For this example, if the current state is 2 and the character being read is a 0 it can transition to either 1,2, or 7. So I think I have to go through all possible transitions to get to the final states. – Prototherian

Answer 1

I think you should transform your automaton into a deterministic one and then do the obvious.

There are three common ways of implementing a finite state machine in software:

• Represent the transition function as a table (2D array) and upon each character read, look up the next state in it.
• Use nested switch statements for the current state and input character to explicitly define the next state in code.
• Use the State Pattern: Represent each state as a class with a method returning the next state, given an input character.

Since you'll need to build your automaton at run-time, the last two options don't really apply, so you should go with the lookup table. If your alphabet is small, you can write down all transitions. If the alphabet is huge, this might waste a lot of space and you can think about table compression which used to be an active field of research.

For the Downvoters: You cannot write a deterministic program that “executes” a non-deterministic automaton. However, by a rather fundamental theorem of theoretical computer science, you can transform any non-deterministic finite state automaton into a deterministic one by a fully automated procedure, that is, a deterministic algorithm that can easily be implemented in software. Every computer science student should have done this procedure at least once using pencil and paper. If you do so, you'll quickly see how to keep track of which states of the original automaton went into which states of the deterministic one. Then, simply simulate the latter one, see in what state it ends up and output the states of the original non-deterministic automaton that constitute it.

Reena

This is for the general case of any auatomaton found in a text file. – Copra

@Copra So is my proposed solution. – Reena

Answer 2

NFA means you can have set of states at a time. So to represent current state of NFA use Set interface.

Set interface guarantees that there won't be any duplicates of state in . This is important as NFA has more than one state at a time. If you use any other data set this gurrentee is not there. In case of NFA chance of having duplicate state in each transition is exponential. But set of state is always finite. Set interface guarantees that your current set will be filled with duplicates.

For space and performance you can use Enumset as Enumset use bit vectors to store state internally.

Algorithm:

initialise to start state

Process string from right to left starting from index 0;

for character at update the using the state transition;

If for any of this transition leads to final state which means that string is accepted.

Mutualism

I have to keep testing it but right now I have a program that seemingly works. I did something similar to this, thanks for leading me in the right direction. – Prototherian