nfa to dfa algorithm

Question

I've read a text file of symbols,states and transition n put it all in a table.It looks like this:
symbols a, b
states q1, q2, q3, q4
start state q4
final state q2, q3

transition state:
q4, epsilon, q1
q1, a, q2
q3, a, q3
q3, b, q1

I've read an algorithm of how to convert it but don't really understand it and how would I create transistion method and what should i have state class?

Answer 1

Do you have a programming problem, or an problem with Automata?

Because programming this it seems very simple. Yes, you'd have a state class, with 4 possible values q1-a4. The state class has a single constructor initializing it to q4. It has an Accept(symbol) function that modifies the state object, and possibly an IsEndState() function that returns true for states q2 and q3.

The NFA/DFA part comes into play in the implementation of the Accept() method. Now it coukd be that you are asked for a programmtic solution to convert an NFA-based implementation of Accept() to a DFA-based implementation of Accept().

Answer 2

i have a nifty link right here: JFLAP

JFLAP is an Java JAR which has some nice visualization included. You can test and transform NFAs/DFAs, do Pummping Lemma Stuff and check various grammars and such... You might give it a try!

Answer 3

redurance beat chek in transition ocuure in dfa and recursively backtracking the string in ndfa. how it will be done in the construction.

Answer 4

These two links should help you:

http://www.win.tue.nl/prose/pres/ploeger-19-10-06.pdf
http://www.cs.sun.ac.za/rw711/documentation/hopcroft2.pdf