Formal Language Theory
A theoretical computer science course taught to Computer Engineering students in the Faculty of Control Engineering. It continued Automata Theory and introduced grammars, formal systems, and the foundations of parsing.
Landmarks
- Institution: Polytechnic Institute of Bucharest, Faculty of Control Engineering
- Programme: Computer Engineering
- Year / semester: year III, semester II
- Format: 2 hours lecture + 2 hours seminar
- Course basis: the textbook Teoria limbajelor formale
Context of the course
If Automata Theory brought before students the idea of a formal model of computation, this second course shifted the emphasis toward language: toward the rules by which symbolic structures are generated, toward the way these structures can be described rigorously, and toward their relation to programs, compilers, and formal systems in general.
In the natural order of things, the course came after automata. In reality, however, it had a distinct identity and a special stake of its own. Here the transition was made from abstract machines and acceptors to grammars, derivations, classes of languages, and the idea that the syntax of a programming language is not merely a practical convention, but a formal construction that can be described, analysed, and processed systematically.
For me, this course meant more than a simple continuation of the previous one. It opened a path that led directly toward one of my later concerns: programming languages and compilers. Once you start teaching formal languages, you can no longer ignore the essential question: how do you move from a grammar to a parser, from a formal definition to an effective implementation?
Structure and main ideas of the textbook
- Introduction to languages and formal systems. The basic concepts are fixed: alphabet, word, language, operations on languages, and the relation between description and generation.
- Formal grammars. The basic definitions appear here: productions, derivations, sentential forms, and the relation between a grammar and the language it generates.
- The Chomsky hierarchy. The textbook orders the classes of grammars and languages in a unified framework: regular, context-free, context-sensitive, and general recursive, showing both the differences and the relations among them.
- Context-free languages. This is one of the central parts, because here lie the basic instruments for describing the syntax of programming languages: derivation trees, ambiguity, grammar transformations, and the relation to pushdown automata.
- Parsing. The course already prepared the ground for compilers: top-down and bottom-up methods, the idea of the parser, and the move from grammar to effective analysis procedures.
- Formal systems and Post systems. The end of the textbook widened the perspective beyond programming languages proper, toward the more general notion of formal system and the role of production rules in symbolic construction.
Significance of the course
For Computer Engineering students, this course had a double function. On the one hand, it provided a rigorous theoretical discipline based on definitions, classes, proofs, and relations between models. On the other hand, it opened a direct path toward fundamental applications of computer science: the syntax of programming languages, parsing, and compiler design.
From this perspective, Formal Language Theory was one of the important links in the formation of a unified vision of the field: automata, languages, computability, compilers. Later, this continuity would also be found in my courses, textbooks, and research on programming languages and compilers.
Connection with my later evolution
Looking back, the course also mattered because it forced me to think more precisely about the relation between syntax and meaning. Even if the main emphasis still fell on grammars and the formal analysis of languages, the ground was already being prepared here for more difficult questions: how meaning is attached to a syntactic structure, how a language becomes a programming tool, and how a compiler is built to treat these different levels systematically.
In this sense, the course was not only a theoretical discipline of its time, but one of the deeper roots of my later direction in languages and compilers.
Materials on the course and textbook
- Overview (PDF) — short description.
- Extended description (PDF) — longer version for readers interested in detail.
- Facsimile / PDF — scanned copy of the textbook.
Links
Chronology: for the biographical and institutional context, see My Path in Research.