Authors :
Shweta, K.Senthil Kumar.
Volume/Issue :
Volume 3 - 2018, Issue 3 - March
Google Scholar :
https://goo.gl/DF9R4u
Scribd :
https://goo.gl/ULXJbC
Thomson Reuters ResearcherID :
https://goo.gl/3bkzwv
Abstract :
This paper deals with the problem of minimization of Deterministic Finite Automata. There are various approaches available for converting the DFA into its minimized DFA for the given input strings. The most efficient algorithm for doing the minimization is the Hopcroft’s Minimization Algorithm which aims at removing all the states which are unreachable i.e. which cannot lead to the goal state with the given set of input symbols. Thereafter, removing or merging all the equivalent states such that the resultant automaton will only have distinguishable states and this automaton would be the minimized automaton for the given input deterministic finite automata. Any two deterministic finite automata will have the same minimized DFA if they represent the same regular language. Here in this project I have attempted to implement the Hopcroft’s algorithm with some parallelism in C language keeping the average time complexity to be logarithmic.
Keywords :
Deterministic finite Automata, NFA, compiler, transition function, equivalent states, distinguishable states.
This paper deals with the problem of minimization of Deterministic Finite Automata. There are various approaches available for converting the DFA into its minimized DFA for the given input strings. The most efficient algorithm for doing the minimization is the Hopcroft’s Minimization Algorithm which aims at removing all the states which are unreachable i.e. which cannot lead to the goal state with the given set of input symbols. Thereafter, removing or merging all the equivalent states such that the resultant automaton will only have distinguishable states and this automaton would be the minimized automaton for the given input deterministic finite automata. Any two deterministic finite automata will have the same minimized DFA if they represent the same regular language. Here in this project I have attempted to implement the Hopcroft’s algorithm with some parallelism in C language keeping the average time complexity to be logarithmic.
Keywords :
Deterministic finite Automata, NFA, compiler, transition function, equivalent states, distinguishable states.
