Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
I am looking for practical applications of Finite State Machines like DFA, NFA, Moore, Mealy machines...
It would be helpful if someone point to examples from Linux Kernel. I know that DFA is used in string matching like KMP algorithm.
What is the significance of NFA, Moore and Mealy machines?
Each time you do a search (particularly a "pattern search") in your favorite editor/tool, the pattern is translated into some form of finite state machine, which does the matching.
The lexical analysis part of your compiler/interpreter (yes, even your shell) is again a finite automaton which matches keywords and other tokens recognized by the language.
Any vending machine is a finite automaton which takes in coins of different denominations and recognizes when the correct amount has been entered (OK, today's vending machines probably have a small CPU inside doing the adding, but the end result is the same).
(the concepts of) DFA/NFA have some applications in the field of compilers and in construction of parsers. They are also use to identify strings according to regular-expressions (i.e. searching "patterns" over the web or over databases)
Moore/Mealy machines, are DFAs that have also output at any tick of the clock. Those have PLENTY of applications. In fact, any CPU, computer, cell phone, digital clock and even your washing machine have some kind of finite state machine in it, that controls it.
Maybe I should make it clear: any "computer" is basically a finite state machine.
One major application is modelling of systems. Essentially, simple software systems can be modeled as Finite State Machines. (By simple software, I mean languages that can be represented using regular expressions). There are many of such "simple" systems, vending machines are examples (as vzn indicated).
By finding the intersection of two Finite state machines, you can design in a very simple manner concurrent systems that exchange messages for instance. As an example, traffic light is a system that consists of mutliple subsytems (the different traffic lights) that works concurrently.
Have a look at these examples: http://www.site.uottawa.ca/~bochmann/SEG-2106-2506/Notes/LTSA-examples/examples/
You will need to have LTSA analyzer to run these examples. http://www.doc.ic.ac.uk/ltsa/
heres a very good online reference on FSMs & related theory, 75p, with many diagrams. has many applications after the middle theory section, and also in many exercises with sample applications eg p485:
ch12. Finite-State Machines by Keller, Harvey Mudd college, CS60 textbook/ CS, intro to abstraction
applications are extremely diverse. eg from the book:
sec 12.4 EE constructions eg
FSMs are also used in speech detection to find phonemes, one of the major points of application of this excellent online library which has some more detail in man pages and documentation: AT&T online FSM library. see section "FSM Library and Speech Processing Applications" (which also lists some more abstract/theoretical "applications")
etc!
I use state machines when writing device drivers. Beware that large state machines can become unwieldy. Consider using this set of macros (https://www.codeproject.com/Articles/37037/Macros-to-simulate-multi-tasking-blocking-code-at) … that way the transitions become so simple that you don’t even need a state diagram. This is because the macros let you write your state machine code as if it is structured code. I wrote Cisco's Transceiver Library for the Nexus 7000 using these macros.
In practice, you will see it explicitly as an integer state variable (usually called 'state') that represents a very coarse state machine representing what actions are callable by the user of an object. It's usually an enumeration with values like: {uninitialized,initialized,...,stopped}. State machines are often explicit when parsing data, and will be signified by a switch statement in a while loop where at the top of the loop, the next character is gotten. In particular, if parsing has a regular grammar, an exact FSM with no other features is often used. If you are in a language that supports tail calls, FSMs are generally exhibited by mutual recursion (which can make the code read like a very clear pseudocode specification). A really useful feature of an FSM is the ability to operate concurrently because you only need to remember current state, rather than an entire execution stack. (ie: context switching between millions of state machine instances).
