1

Minimizing a discrete finite automata is a standard problem in computer science. What are the benefits of minimizing a finite automata? Is it just an academic problem?

Warwick Masson
  • 883
  • 7
  • 17

4 Answers4

1

The principal reason to minimize a finite automaton is to save the implementation cost. When finite automata were being studied, it was with respect to the machines that implemented the function being studied. When an inverter or gate or memory component consisted of one or more vacuum tubes, http://en.wikipedia.org/wiki/Vacuum_tube - devices that cost money, consumed power and took up considerable space, you really, really wanted to reduce the number of tubes and the connections between them.

Even with the move to solid state implementations, real estate was often a concern. If a particular finite automaton was reused frequently in a system, optimizing the FA paid big dividends in chip yields.

Bob Dalgleish
  • 8,167
  • 4
  • 32
  • 42
  • 2
    You seem to be suggesting that minimal FAs are of historical interest only. That's nonsense. In NLP and compiler construction, FAs are still quite pervasive, and non-minimized FAs can still become too large to store/handle efficiently. – Fred Foo May 18 '13 at 12:53
  • 1
    I agree that FA optimization is part of current practice. I was trying to convey a sense of what was at stake in such practice. Additionally, I would like to point out that optimization is not quite the same as minimization -- you want to minimize an FA with respect to the primitives available in your tool set, not just make it the FA with fewest rules, etc. – Bob Dalgleish May 18 '13 at 18:23
  • I don't understand what you mean by "with respect to the primitives available in your tool set." FA minimization is a well-defined problem, independent of any implementation. – Fred Foo May 19 '13 at 11:50
  • Some types of devices are cheaper to implement or easier to lay out than others. The optimization algorithms used in IC layout applications have these rules built in to them and optimize based on the technology. – Bob Dalgleish May 19 '13 at 13:09
1

minimized automata always preferable: (1) efficient(same algorithm if you apply on minimized automate) (2a) need less elements to implement (2b) smaller in size (2c) cheaper (3) sometime obvious to answer(redundant states may be reason of unnecessary complexity)

Grijesh Chauhan
  • 57,103
  • 20
  • 141
  • 208
0

Minimization of a finite automata helps in reducing the compile time, as it removes identical operations.

When we minimize an expression,we tend to remove the unused states or we merge two or more states into a single equivalent state which are likely to produce same output. Merging states like this should produce a smaller automaton that accomplishes exactly the same task as our original one. (Here the unreachable states are removed and the states are checked whether they are distinguishable or not. If undistinguishable the states are merged else the states are uniquely represented).

As it reduces the compilation time,results in increasing the processing speed of the program. Running a program which can run a second or two faster than other programs, can vastly increase the scope of the program. Therefore minimization is very essential in the process.

Manasa Lakshmi Nutakki
  • 1
  • 1
0

First of all, minimization of a finite automata is very useful in making the compilers execute faster, as it removes identical operations.

When we minimize an expression, we merge two or more states into a single equivalent state.

Merging states like this should produce a smaller automaton that accomplishes exactly the same task as our original one.

This is very much required to reduce the whole total compilation time and eventually increase the processing speed of the program.

Running a program which can run a second or two faster than other programs, can vastly increase the scope of the program.

Therefore minimization is very essential in the process.

Prasanth Sekhar Rayudu
  • 1