CS 360
Introduction to the Theory of Computing
Winter 2017
Practical Applications of CS 360

Efficient tokenization of computer languages: the first
step in compilation is breaking the input up into tokens. The
best methods rely on the theory of regular expressions.
 Efficient compilation of computer languages: we want to
write our computer programs in a highlevel language and have
them parsed automatically translated to machine code. The best methods
for this rely on the theory of deterministic contextfree languages
and LR grammars.
 String searching: more and more, we must search vast
databases of text for data matching a given pattern, which can
have wildcards and other distinguished symbols. Many stringsearching
methods are ultimately based on finite automata and regular
expressions.

Recognizing difficult problems: in real life, one is
sometimes confronted with the necessity of solving an undecidable
problem. The theory of computation helps you
recognize when the problem you want to solve has no general solution,
and lets you look for alternatives
to solve the problem (approximate solutions, etc.)
 Applications to other areas: formal language theory has
proven useful in many other fields, such as
 circuit verification
 modelchecking (formal verification of finitestate
concurrent systems)
 XML document checking
 economics and game theory (finite automata as strategy
models in decisionmaking);
 theoretical biology (Lsystems as models of
organism growth; DNA as a string)
 computer graphics (Lsystems)
 linguistics (modeling by grammars)
Back to CS 360 home page