0
$\begingroup$

I need to choose a language, design a finite automaton M such that L = L(M). Construct a minimum-state DFA M′ equivalent to M in such a way that the ratio of the number of states in M to the number of states in M′ is less than 0.5.

I have zero idea as to how I should approach this. I've tried considering a few DFA's, as its the best place to start, considering that NFAs obviously have fewer states than their corresponding DFAs, but I'm not able to think of an approach to derive or contemplate a DFA with it's minimal counterpart having states < 0.5 times number the original DFA.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ Take any minimal DFA and add as many dummy states as you want. $\endgroup$
    – Yuval Filmus
    Feb 26, 2018 at 22:31
  • $\begingroup$ @YuvalFilmus, my title is wrong, Apologies. Will correct it. Description is the opposite to the title. $\endgroup$
    – Vishhvak Srinivasan
    Mar 4, 2018 at 20:06

1 Answer 1

Reset to default
4
$\begingroup$

What the question is really asking you is:

How much saving can be achieved by "compressing" a DFA to its equivalent minimal DFA?

The answer is: the amount of saving which can achieved is unbounded. There are (at least) two ways to measure the saving:

  1. Number of states which are eliminated.
  2. Number of states in the new automaton as a fraction of the original number of states.

The number of states which are eliminated is unbounded, and the number of new states as a fraction of the number of original states can be arbitrarily close to zero.

An example is not hard to come by: pick you favorite minimal DFA, and add as many dummy states as you want. These dummy states will not be reachable from the initial state of the original DFA, so thy won't affect the language accepted by the DFA; but they will increase the number of states by an amount of your choice.

What if we disallow this example by asking all states in the DFA to be reachable? What if ask, moreover, that there be an accepting state reachable from any state? (This makes sense as stated if we're allowing the DFA to get stuck, in other words, for the transition function to be a partial function; but a similar condition can be defined for DFAs with total transition functions.) The statements above still hold true, and an example is not difficult to come up to. I challenge the readers to figure out such an example.

Improve this answer
$\endgroup$
3
  • $\begingroup$ This is brilliant. Thank you so much! That aside, I am not able to understand the reasoning around how it makes sense to the question of having an accepting state reachable from any state. Could you please clarify? $\endgroup$
    – Vishhvak Srinivasan
    Feb 27, 2018 at 16:40
  • $\begingroup$ You can say that a state is redundant if whenever the automaton reaches it, it is guaranteed not to accept the word. There is no reason to have more than one such state. $\endgroup$
    – Yuval Filmus
    Feb 27, 2018 at 17:31
  • $\begingroup$ As edited, what If I need an FSA (other than a DFA, obviously), where on converting it to its minimal DFA, I get more states than the original FSA I started with, as in, the ratio of the number of states of the original FSA to the number in the minimal DFA < 0.5? $\endgroup$
    – Vishhvak Srinivasan
    Mar 5, 2018 at 9:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.