patternMinor
Real life applications of finite automata
Viewed 0 times
realfiniteautomataapplicationslife
Problem
I have some confusion about the differences between finite & infinite.
can someone tell me how the Toll machine or Park meter, soda vending machine can be used with infinite language? if not, please give me an example of other application.
can someone tell me how the Toll machine or Park meter, soda vending machine can be used with infinite language? if not, please give me an example of other application.
Solution
As Yuval Filmus said, the KMP substring matching is widely used in practice because of its modularity and efficiency.
A maybe more "practical" exemple is lexical analysis.
(https://en.wikipedia.org/wiki/Lexical_analysis)
Depending on your application (let say or the compilation of a programming language) the parsing phase can be done with some various
generalisation of automatons (state transition machines or pile-automatons for instance). The language they accept is infinite (think of the set of all programs that are syntactically correct in your favorite language), yet
the recognition of a correct program should be done by an automata (or a generalisation of it) which is finitely presented.
A maybe more "practical" exemple is lexical analysis.
(https://en.wikipedia.org/wiki/Lexical_analysis)
Depending on your application (let say or the compilation of a programming language) the parsing phase can be done with some various
generalisation of automatons (state transition machines or pile-automatons for instance). The language they accept is infinite (think of the set of all programs that are syntactically correct in your favorite language), yet
the recognition of a correct program should be done by an automata (or a generalisation of it) which is finitely presented.
Context
StackExchange Computer Science Q#90418, answer score: 4
Revisions (0)
No revisions yet.