0
$\begingroup$

This question relates with this question and answer.

May I know why "Writing a structured program for any tangle of an automaton is possible in principle, but probably not worth the hassle (translating arbitrary transfers of control into a nice structure -- for some non-trivial value of "nice" -- is a lot of work, and making sure both check out even more so)" and why "it's rarely done in practice"?

Does that mean automaton is not useful in practice (real coding)? In terms of translating the automaton into a code. If not useful, then what is used in practice? Is automaton still useful in problem solving though?

$\endgroup$
1
  • 1
    $\begingroup$ At least one field where finite automatons (and automaton-like structures, e.g. Moore machine) are useful is model checking: they are one of the rare cases when you really can verify the correctness of the program. Also, the way some physical systems are organized actually facilitates an automaton-like representation (to make it really finite, you usually want to use discretization of real variables). $\endgroup$
    – user114966
    Sep 21 '20 at 9:56
1
$\begingroup$

While solving common programming tasks it's usually not helpful to think of an automaton. But there are still many cases where they are applied:

  • writing small parsers (e.g. parse an integer/float); in order to not forget edge cases drawing an automaton is really helpful; for more complicated parsers grammars are usually a better tool
  • state machines are often encountered in game programming (e.g. to manage which animation is currently executing; e.g. press the UP key switches the animation state machine in walking up mode; or to manage game states like if are you currently in-game or in the main menu)
  • important (string) algos such as the KMP string matching algorithm use an automaton in the background but it's usually represented as a table and quite hard to wrap your mind around

Automatons are models that are theoretically useful to prove properties of language classes. To make proves as simple as possible their definition is also kept simple. In day to day code you usually stitch together powerful high level data structures to solve your problems and don't think on the low level of e.g. a Turing Machine that would manipulate input on the bit level but rather in terms of higher data types such as ints and lists.

P.S. Automatons are very useful for designing circuits, since circuits work on the bit level and you usually try to minimize the components used it's useful to note down which states your circuit needs and how it should transition between them given some small binary input.

$\endgroup$
2
  • $\begingroup$ Thank you so much for your insight :) Regarding the "automata for designing circuits", is that "logic automata" or something else? $\endgroup$
    – kate
    Sep 22 '20 at 5:13
  • 1
    $\begingroup$ I was actually thinking of computer science in high school where we were introduced to simple circuits with flipflops. The teacher always wanted us to make a state transition graph. This graph is basically a simple DFA where the states encode which flipflop are on and which off and the transitions between the states are the inputs to the circuit. e.g. you can make a DFA which is accepting when it gets an even amount of 1s as input. With this DFA you can come up with a clocked circuit that does the same thing. $\endgroup$
    – plshelp
    Sep 22 '20 at 5:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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