Automata Theory
A theoretical computer science course taught to Computer Engineering students in the Faculty of Control Engineering. It introduced finite and infinite automata, regular languages, the Turing machine, and the first major notions of computability.
Landmarks
- Institution: Polytechnic Institute of Bucharest, Faculty of Control Engineering
- Programme: Computer Engineering
- Year / semester: year III, semester I
- Format: 2 hours lecture + 2 hours seminar
- Course basis: the textbook Teoria automatelor
Context of the course
This was one of the courses through which theoretical computer science entered the engineering curriculum in an explicit and systematic way. It introduced the student to the idea that computation can be studied through abstract machines and formal models, not only through concrete hardware and practical programming languages.
For me, the course also had a formative importance of its own. It forced me to organize a field that was new in the local curriculum and to provide students with a coherent support. That is how the textbook Teoria automatelor came into being.
Structure and main ideas of the textbook
- Part I – Introduction. It establishes the basic vocabulary (states, transitions, inputs/outputs) and the finite / infinite distinction, as a conceptual threshold before formalization.
- Part II – Theory of finite automata. It develops the mathematical and technical apparatus: definitions, representations, relations between automata, equivalences, partially defined automata, realization, and the automaton as acceptor, that is, the link between automata and languages.
- Structure of finite automata. It treats the “black box”, the interconnection of automata, substitution, partitions and reduction, as well as serial and parallel decompositions. The end of this part prepares the transition toward languages: Kleene’s theorem, regular expressions, and the nondeterministic finite automaton.
- Part III – Infinite automata. Computability. It introduces the Turing machine (definition, examples, simulation, universal machine), discusses the limits of computability, especially the halting problem, and relates Turing computability to the theory of recursive functions (primitive recursive, minimization, general recursive).
Significance of the course
The course was not conceived as a mere collection of definitions and theorems. Its purpose was to offer the future computer engineer a discipline of rigour: to understand what a formal model is, how the behaviour of a symbolic system is expressed, and where the limits of effective computation lie.
In this sense, Automata Theory opened the way toward domains that later became important in my activity: formal languages, compilers, the semantics of languages, and, more broadly, the idea that software design needs precise abstract models.
Materials on the course and textbook
- Overview (PDF) — short description.
- Extended description (PDF) — a longer version for readers interested in detail.
- Facsimile / PDF (Parts I and II).
- Part III (PDF).
Links
Chronology: for the biographical and institutional context, see My Path in Research.