patternMinor
Practical application of Finite State Machines
Viewed 0 times
finiteapplicationstatemachinespractical
Problem
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?
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?
Solution
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 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).
Context
StackExchange Computer Science Q#10280, answer score: 8
Revisions (0)
No revisions yet.