ABSTRACT
Theoretical computer science is concerned with modeling computational problems and solving them algorithmically. It strives to distinguish what can be computed from what cannot. The objective of a computer is ultimately to make logical decisions and to calculate the values of functions. Any decision problem can be represented as recognizing whether an input string is in a specified subset; calculating a function amounts to accepting an input string and producing an output string. A language is a set of strings that are used within some domain of discourse, and a grammar is a system for generating a language. A grammar is what enables a compiler to determine whether a body of code is syntactically correct in a given computer language. Applications of formal language theory range from natural and programming languages, developmental biology, and computer graphics, to semiotics, artificial intelligence, and artificial life.
