Appendix A

Formal Languages and Automata

In this appendix, we discuss essential portions of Formal Languages and Theory of Automata. The other names for these topics are “Theory of Computation” and “Mathematical Theory of Computer Science”.

The topics discussed concern basic mathematical properties of computer hardware, software and some applications. Though they have purely mathematical and philosophical aspects, we discuss the topics from viewpoint of their connections with computer science and specifically, language processors.

For example, study of grammars (e.g. Section A .3) will be useful to those trying to design a new programming language for some special application. For those concerned with pattern matching, ideas covered under Regular Expressions and Finite-state Machines will be useful.