MATH 472BAbstract Models of Computation
- Faculty
- Mathematics
- Last listed
- 1975–76
No longer offered. It’s in Waterloo’s scanned calendars from 1975–76 to 1975–76 (before that, 1968–69 to 1972–73 used the number for Introduction to Automata Theory and Introduction to Turing Machines and Computability Theory); the 1995–96 to 2023–24 calendars are on ucalendar.
Models of the computational process as reflected by computers, linguistic systems, functional specifications, transformational systems, formal logic, etc. Equivalence of these models. Computational complexity for specific models and abstractions fitting all models. Formal] reducibilities between computational problems, and the complexity of these reducibilities. 3 hours lectures, Winter term 472¢ Theory of Context Free Languages and Parsing Languages and their representations. Grammars ~ Chomsky hierarchy. Regular sets and sequential machines, Context-free grammars — normal forms, basic properties, Pushdown automata and transducers. Operations on languages. Undecidable problems in language theory. Applications to the design of programming languages and compiler construction. 3 hours lectures, one term Offered in the Spring and Fall terms
As printed in the 1975–76 calendar, read by OCR; the scanned page is the original.
Requirements, as last listed
Prerequisite: Math 3726
Prerequisite: Math 372b
Check it elsewhere
In the scanned calendars
How it read in each calendar from 1968–69 to 1975–76, newest first. The text is OCR of the scanned pages; years whose wording matches are shown once, from the clearest scan. Each year links to its page on uwloo and to that page of the scanned PDF.
1975–76 1 calendar
Models of the computational process as reflected by computers, linguistic systems, functional specifications, transformational systems, formal logic, etc. Equivalence of these models. Computational complexity for specific models and abstractions fitting all models. Formal] reducibilities between computational problems, and the complexity of these reducibilities.
3 hours lectures, Winter term
472¢ Theory of Context Free Languages and Parsing Languages and their representations. Grammars ~ Chomsky hierarchy. Regular sets and sequential machines, Context-free grammars — normal forms, basic properties, Pushdown automata and transducers. Operations on languages. Undecidable problems in language theory. Applications to the design of programming languages and compiler construction.
3 hours lectures, one term
Offered in the Spring and Fall terms
Prerequisite: Math 3726
Prerequisite: Math 372b
Not in the 1973–74 to 1974–75 calendars.
1969–70 to 1972–73 4 calendars
Another title: Introduction to Turing Machines and Computability Theory, probably a different course under the same number (or a misread scan).
Formalisms of Turing machines. Variants of Turing machines. Universal Turing machines. Unsolvability of the halting problem and related results. Recursive and primitive recursive functions. Models similar to digital computers. Brief introduction to formal languages. Post’s symbol-manipulation systems. Simple bases for computability. Prerequisite: Mathematics 427a or Consent of Instructor. 2 hours lectures, Winter term.
1968–69 1 calendar
Another title: Introduction to Automata Theory, probably a different course under the same number (or a misread scan).
Sequential machine models. Reduction of completely and incompletely specified machines. Realization of machines. The secondary assignment problem. Decomposition of machines. Finite automata and regular events. Introduction to Turing machines and computability. Introduction to formal languages.
2 hours lectures, Winter term.
Prerequisite: Switching Circuits.