Any common problems solvable by DFA/NFA or PDA except recognizing languages? 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:


problems like those in algorithm analysis and data structures, i.e. sorting, shortest path, etc.
functions seen in the everyday work of a common programmer, probably some useful business logic.
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.