Automaton Determinisation and Reduction algoritm
This is just out of curiosity, but have any of you ever try to code algorithms to go from a NDFA(Non-Deterministic Finite Automaton) into a DFA(Deterministic Finite Automaton), or I'de say those that define regular language?. What is that O (or even better, the Theta of it) of it? What about an algorithm to pass from a DFA to a Reduce Deterministic Finite Automatons?.
Mind you I am not talking about Stack Automaton (which define grammar, but not necerraly regular language), because I don't think this was solve as of today, or at least if I remember correctly, mathematical definitions of it were still in early stage, so it was hard to "bound" such automaton.
This is just a student curiosity in work here. :)
Those who know what are automatons will know what I am talking about :)
[814 byte] By [
evanzsa] at [2007-9-29 7:38:53]
>What is that O (or even better, the Theta of it) of it?
if you have a NFA with n states, then the equivalent DFA can have 'exponential in n' states (worst case) - don't know what the exponent is
i've not coded this in java, but it shouldn't be too different - what do you have so far?
asjf
asjfa at 2007-7-14 21:30:07 >
The exponent is 2, by the power-set construction. Each state in the DFA is a member of the power set of the states in the NFA. There is a transition under character a from state {Ai : i in I} to state {Aj : j in J} iff forall i in I: exists j in J such that i --a--> j and forall j in J: exists i in I such that i --a--> j. The initial state of the DFA is the set of all initial states of the NFA, and the accepting states of the DFA are any states containing an accepting state of the NFA. Proof of the construction (which may uncover the odd error - I've done it from first principles in about 2 minutes) is left as an exercise to the reader, as are optimisations.
> i've not coded this in java, but it shouldn't be too
> different - what do you have so far?
>
> asjf
I didn't do anything... I was just curious about the efficiency of such algorithm. I've study automaton, language and grammar last semester, but I was wondering if it was not a NP complete problem..
