3
$\begingroup$

I understand that DFAs recognize regular languages, and PDAs context-free languages, but these are a little bit too theoretical. I am wondering if we can implement common functions or solve common problems with DFAs and PDAs instead of Turing machines (or in a Turing-complete language).

By "common", I mean either one of the following:

  1. problems like those in algorithm analysis and data structures, i.e. sorting, shortest path, etc.
  2. functions seen in the everyday work of a common programmer, probably some useful business logic.
$\endgroup$
  • 2
    $\begingroup$ Compilers use DFAs and PDAs to parse the input. Does that count? $\endgroup$ – Yuval Filmus May 9 '18 at 13:11
  • 1
    $\begingroup$ Using DFAs you can answer questions like this: Suppose I toss a coin with bias H=0.6. What is the probability that in 100 tosses there will be no run of heads of size 10? $\endgroup$ – Yuval Filmus May 9 '18 at 13:12
  • $\begingroup$ There are even chips implementing NFAs. These are called Automata Processors: pdfs.semanticscholar.org/5fe6/…. These are useful for networking. $\endgroup$ – Yuval Filmus May 9 '18 at 13:24
  • 1
    $\begingroup$ @YuvalFilmus I think compilers are examples of recognizing regular expressions (lexing part) and context-free languages (parsing part). And since a lot of networking protocols like TCP are just internally finite state machines, it is not very surprising that the logic is transitioning to hardware. However, would you mind elaborate on the coin-tossing example? $\endgroup$ – wlnirvana May 9 '18 at 14:24
  • 2
    $\begingroup$ Always good in this context to point at this great answer to What is the enlightenment I'm supposed to attain after studying finite automata? at our grown-up sister site cstheory. $\endgroup$ – Hendrik Jan May 9 '18 at 18:38
1
$\begingroup$

In imperative programming, state machines are quite common, and they usually look more or less like the following pseudo-code:

state = INITIAL_STATE;

while (token = read_an_input_token(input))
{
   if (state == STATE_1)
   {
      if ([some condition on the token])
      {
         [some actions]
         state = [some state]
      }
      else if ([another condition on the token])
      [etc.]
   }
   else if (state == STATE_2)
   [etc.]
}

if (state != ACCEPTING_STATE)
{
   [error handling, perhaps abort]
}
else
{
   [apply finishing touches]
}

All kinds of variations may occur: you'll see case statements being used in languages that have them, the order in which the conditions are tested and the way they are grouped may vary, more input scanning may occur than just reading separate tokens, et cetera.

You're likely to see similar loops wherever a regular language needs to be parsed. For instance, command line utilities usually parse their arguments in this way. (Mine do, anyway.)

There are other approaches to using state machines in software; I think this is the most popular and most informal one.

$\endgroup$
  • $\begingroup$ Thanks for the enlightening answer which helped me realize that a lot of high-level workflows can be abstracted into automata. Yet I'm only half satisfactory with the answer, because the low level details like some condition and some actions may involve Turing machine power. $\endgroup$ – wlnirvana May 10 '18 at 7:49
  • $\begingroup$ @winirvana: yes; so what? $\endgroup$ – reinierpost May 11 '18 at 4:29
  • $\begingroup$ Sorry, that came out wrong ... what I mean is: surely there are cases in which you really don't want any more power than what a finite state machine provides, but in many cases, you don't mind. What is your specific reason for not being happy with this approach? $\endgroup$ – reinierpost May 15 '18 at 16:29
  • $\begingroup$ Never mind. And I am sorry too for being picky as well as not clear, but I was considering to demonstrate powers of different computation models to middle school students, with very concrete examples. That's why I wanted "pure" examples. $\endgroup$ – wlnirvana May 17 '18 at 4:06
  • $\begingroup$ For purer examples, consider state-machine-model-based development techniques. Such techniques specify a system as a state-machine based model, then you fill in the details with code. This is popular in industry for streaming/dataflow architectures. I've seen many examples of development tools and libraries based on this approach, e.g. Simulink and ROS. When done properly, this approach allows you to derive runtime properties of the behavior of your system. $\endgroup$ – reinierpost Sep 7 '18 at 9:38

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.