CODEWITHSUNDEEP
finite-automatastate-machineformal-languages
Nawal Haider Mirza
Nawal Haider Mirza

Reputation: 29

How to determine the number of states of finite automata according to any language?

I have a burning question about finite state machines, that how we can know that this language needs 2 states or 3 states? I mean is there any formula for that? Although I believe, we would always work to minimize the number of states but still How can we determine the number of states to be created according to any language or string (without actually constructing the DFA)?

Upvotes: 2

Views: 3866

Answers (2)

Cybercartel
Cybercartel

Reputation: 12592

Aho-corasick multiple pattern matching algorithm is a finite state machine with only 1 state.

Upvotes: 0

John Coleman
John Coleman

Reputation: 51998

You are in effect asking about DFA minimization. It is a well-studied problem for which a number of algorithms have been developed. The Wikipedia article on it is a good starting point.

The theoretical result which governs the number of states is the Myhill-Nerode theorem, but this theorem doesn't give any quick formula. You have to determine the number of equivalence classes in an equivalence relation defined in terms of the language. Hopcroft's algorithm for DFA minimization is essentially an algorithm for determining the equivalence classes in the Myhill-Nerode equivalence relation. I suspect that any attempt to use Myhill-Nerode more directly is going to lead to something similar to Hopcroft's algorithm, though I am not an expert in the field.

Upvotes: 2

Related Questions