CS 360
Introduction to the Theory of Computing
Winter 2019

Practical Applications of CS 360

  1. 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.

  2. Efficient compilation of computer languages: we want to write our computer programs in a high-level language and have them parsed automatically translated to machine code. The best methods for this rely on the theory of deterministic context-free languages and LR grammars.

  3. 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 string-searching methods are ultimately based on finite automata and regular expressions.

  4. 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.)

  5. Applications to other areas: formal language theory has proven useful in many other fields, such as

Back to CS 360 home page