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.


1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.