Applications of Finite Automata

String Processing
Consider finding all occurrences of a short string (pattern string) within a long string (text string). This can be done by processing the text through a DFA: the DFA for all strings that end with the pattern string. Each time the accept state is reached, the current position in the text is output.

Finite-State Machines
A finite-state machine is an FA together with actions on the arcs.

State charts
Statecharts model tasks as a set of states and actions. They extend FA diagrams.

Lexical Analysis

In compiling a program, the first step is lexical analysis. This isolates keywords, identifiers etc., while eliminating irrelevant symbols. A token is a category, for example “identifier”, “relation operator” or specific keyword.

Leave a Reply