Java – implement a nondeterministic finite automata (NFA)

I am trying to develop a simulation of non - deterministic finite automata in Java The first command - line argument is a text file that defines the machine The second parameter is the input string If it accepts strings, it prints to the standard output "accept", followed by a list of acceptable states that can be ended If it rejects, it outputs "reject" and then a list of all possible end states

For example, 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

Look like:

An input string of 10 will be output

reject 1 2

And output an input string 000

accept 7

I need to suggest what data structure to use I thought about using hashmaps and sets, but I'm not sure

Solution

I think you should turn your automata into a deterministic automata and do something obvious

There are three common methods to implement finite state machine in software:

>Represent the conversion function as a table (2D array) and find the next state when each character is read. > Use nested switch statements for the current state and input characters to explicitly define the next state in the code. > Use state mode: when an input character is given, each state is represented as a class using a method that returns the next state

Since you need to build automata at run time, the last two options are not really applicable, so you should use lookup tables If your alphabet is small, you can write down all transitions If the alphabet is large, it may waste a lot of space. You can consider table compression, which used to be an active research field

For downvoters: you can't write a deterministic program that "executes" a nondeterministic automata However, through a fairly basic theorem of theoretical computer science, you can convert any non deterministic finite state automata into deterministic automata through a fully automated process, that is, deterministic algorithms that can be easily implemented in software Every computer science major should complete the program at least once with pencil and paper If you do this, you will soon see how to track which states of the primitive automata enter which states of the deterministic state Then, simply simulate the latter, look at its end state, and output the state of the original nondeterministic automata that constitutes it