We begin by defining what is a language and in particular what is formal language. Fundamental descriptive devices for computer languages are introduced and covered in detail. This includes regular expressions, grammars, and automata. For the latter type, we ll also look at such related topics as simplification, ambiguity, and normal form. Three types of automata are described- finite automaton, the pushdown automaton, and the Turing machine.
Formal language is among the most abstract and theoretical of all computer science courses.
You will learn how to define language by an abstract mathematical structure and be introduced to a variety of proof techniques. Most theorems will be carefully gone over in class. In some cases, long and tedious proofs are omitted due to time constraints. Numerous examples are provided, in class and as homework, as illustrative applications of the underlying theory. The emphasis is placed on ideas and understanding rather then on undue formalism and rote memorization.