CS4-Theory of Finite Automata (4.5+3)


Undergraduate course in finite automata theory with introduction to formal languages.

Lecturers

J.A. Garcia and S. Moral.

Goal

The three major foundations of computer science, the mathematical description of computational networks, the limitations of mechanical computation, and the formal specification of languages are highly interrelated disciplines, and all require a great deal of mathematical maturity to appreciate. A computer science undergraduate is often expected to deal with all these concepts, and so, this course attempts to make it possible for the average student by developing the standard mathematical models of computational devices, as well as investigating the cognitive and generative capabilities of such machines. The engineering viewpoint is addressed. Further information can be found in the program for the course given the spring 1996 .

Contents

Introduction to the notion of finite state machines and their use to recognize strings in a language. Finite deterministic automata (FDA). Definition of regular languages as those accepted by FDAs. Examples. Finite non-deterministic automata (FNA). Proof that the class of languages accepted by FNAs coincides with the regular languages.

Operations on regular languages: finite union and intersection, concatenation, and Kleene closure. Regular expressions and the regular languages they denote. Proof that a language is regular if and only if it is denoted by a regular expression (Kleene's Theorem). The Pumping Lemma. Examples of languages that are not regular. Minimization of finite automata. Algorithms.

Finite-State Transducer. Moore Sequential Machines. Transducer applications. Context-free languages. Parse Trees. Ambiguity. Canonical forms. Pumping Theorem. Closure Properties. Pushdown automata. Pushdown automata and context-free languages. Closure Properties and DPA. Parsing. LR parsing. LL parsing.

Literature

Materials


© J.A. García ; jags@decsai.ugr.es