Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
Concept
DFA minimization
Summary
In automata theory (a branch of theoretical computer science), DFA minimization is the task of transforming a given deterministic finite automaton (DFA) into an equivalent DFA that has a minimum number of states. Here, two DFAs are called equivalent if they recognize the same regular language. Several different algorithms accomplishing this task are known and described in standard textbooks on automata theory.
For each regular language, there also exists a minimal automaton that accepts it, that is, a DFA with a minimum number of states and this DFA is unique (except that states can be given different names). The minimal DFA ensures minimal computational cost for tasks such as pattern matching.
There are three classes of states that can be removed or merged from the original DFA without affecting the language it accepts.
Unreachable states are the states that are not reachable from the initial state of the DFA, for any input string. These states can be removed.
Dead states are the states from which no final state is reachable. These states can be removed unless the automaton is required to be complete.
Nondistinguishable states are those that cannot be distinguished from one another for any input string. These states can be merged.
DFA minimization is usually done in three steps:
remove dead and unreachable states (this will accelerate the following step),
merge nondistinguishable states,
optionally, re-create a single dead state ("sink" state) if the resulting DFA is required to be complete.
The state of a deterministic finite automaton is unreachable if no string in exists for which . In this definition, is the set of states, is the set of input symbols, is the transition function (mapping a state and an input symbol to a set of states), is its extension to strings (also known as extended transition function), is the initial state, and is the set of accepting (also known as final) states.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.