A Critical Analysis of Performance and Efficiency of Minimization Algorithms for Deterministic Finite Automata

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

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.


Paper Submission Last Date
28 - February - 2023

Paper Review Notification
In 1-2 Days

Paper Publishing
In 2-3 Days

Video Explanation for Published paper

Never miss an update from Papermashup

Get notified about the latest tutorials and downloads.

Subscribe by Email

Get alerts directly into your inbox after each post and stay updated.

Subscribe by RSS

Add our RSS to your feedreader to get regular updates from us.