 |
Automata & Formal Languages |
|
Automata & Formal Languages |
| Lecturer. | Professor Benedikt Löwe, e-mail: b(dot)loewe(at)dpmms(dot)cam(dot)ac(dot)uk | ||
| Time. | Monday, Wednesday, Friday 12pm. | ||
| Room. | MR3. | ||
| Example Sheets. |
Example sheets for the course are available at http://www.dpmms.cam.ac.uk/study. | ||
| Lecture Notes. | The handwritten lecture notes of each lecture can be found at the end of the brief lecture summary. In addition, there is a pdf file with the typed notes (last changed: 21 November 2023): pdf file. | ||
| L E C T U R E S. | |||
| Week 1. |
First Lecture. Friday, 6 October 2023. Theory of computation: decision problems, non-uniform solutions vs. uniform solutions. Examples for solvable decision problems: Is a number prime? Is a matrix invertible? Hilbert's 10th problem. The Entscheidungsproblem. Unsolvability of Hilbert's 10th problem and the Entscheidungsproblem
(no proof). General set-up: symbols, strings. Notation: strings and sequences, length of sequences, concatenation of sequences. Lecture Notes. | Second Lecture. Monday, 9 October 2023. More notation. Infinite and countable sets. Basic countability and uncountability results for sets. Natural languages; Chomsky's claim that recursion is the most salient feature of language; grammaticality is independent of whether we can assign meaning to sentences. Rewrite rules and rewrite systems. There are only countably many rewrite systems. Derivations. Grammars. Generated language of a grammar. Example of a grammar with its language. Lecture Notes. | Third Lecture. Wednesday, 11 October 2023. Detailed proof of the example. How do we prove that something is not derivable? Other examples of grammars producing the same language: equivalence of grammars. Isomorphisms between grammars. Only the size of the set of variables matters. There are only countably many languages generated by a grammar. The Chomsky hierarchy: noncontracting, context-sensitive, context-free, and regular production rules, grammars, and languages. The empty word cannot be produced by noncontracting grammars. Lecture Notes. |
| Week 2. | Fourth Lecture. Friday, 13 October 2023. Examples of equivalent grammars belonging to different Chomsky types. Properness of the Venn diagram of Chomsky types: there are languages that are not type 0 and there are type 3 languages; all other areas need to be populated by examples (will do that during this lecture course). Decision problems: word problem, emptiness problem, equivalence problem. Restricted decision problems for Chomsky types. The word problem for noncontracting grammars is solvable; thus, the word problem for type 1, 2, and 3 grammars is solvable. Closure properties: concatenation, union, intersection, difference, complement. Relationship between closure properties. The concatenation grammar and the union grammar. Variable-based grammars. Closure of type 1 and type 2 languages under union and concatenation. Lecture Notes. |
Fifth Lecture. Monday, 16 October 2023. Detailed proof that the union grammar produces the union (under the assumption of variable-based rules and disjoint variable sets). Remark about producing the empty word: the basic \(\varepsilon\)-rule, \(\varepsilon\)-adequate grammars, essentially regular, context-free, and context-sensitive languages. Analysis of regular derivations. The regular union and concatenation grammars. Detailed proof that the regular concatenation grammar produces the concatenation (under the assumption of disjoint variable sets). Deterministic automata. Lecture Notes. | Sixth Lecture. Wednesday, 18 October 2023. Recursive definition of \(\widehat{\delta}\). State sequences. Graphical representation of deterministic automata as labelled directed graphs. Homomorphisms between automata. Homomorphic automata give the same language. Languages accepted by an automaton are regular. Remark about automata accepting \(\varepsilon\). Non-deterministic automata. State set sequences. Regular languages are accepted by a non-deterministic automaton (construction of the non-deterministic automaton). Lecture Notes. |
| Week 3. | Seventh Lecture. Friday, 20 October 2023. Regular languages are accepted by a non-deterministic automaton (proof that the automaton accepts the language). Subset construction. Equivalence of being regular, being accepted by a deterministic automaton, and being accepted by a non-deterministic automaton. The regular pumping lemma. Regular languages satisfy the regular pumping lemma. Applications: non-regular languages; regular languages without small automata. Example of a context-free language that is not regular. Lecture Notes. | Eighth Lecture. Monday, 23 October 2023. Non-regular languages that satisfy the regular pumping lemma exist. Closure properties: complementation, intersection. Alternative proof of closure properties: product automata for union and intersection. Regular expressions: Kleene star and plus, recursive definition of regular expressions, assignment of languages. Characterisation theorem: reduction of the first direction to closure of regular languages under Kleene plus. Beginning of the proof of that closure. Lecture Notes. | Ninth Lecture. Wednesday, 25 October 2023. Proof that regular languages are closed under Kleene plus. Automata of minimal size. Indistinguishable and inaccessible states. Sufficient conditions for an automaton homomorphism to be injective or surjective. Irreducible automata that are homomorphic are isomorphic. The clean-up automaton (removing inaccessible states). The quotient automaton (removing indistinguishable states). Every reducible automaton has a strictly smaller irreducible automaton. All automata of minimal size are irreducible. All irreducible automata accepting the same language are isomorphic (start of proof). Lecture Notes. |
| Week 4. | Tenth Lecture. Friday, 27 October 2023. All irreducible automata accepting the same language are isomorphic (end of proof). Minimalisation theorem. Solving the emptiness and equivalence problem for regular grammars: isomorphism problem, accessibility, and indistinguishability problems are solvable. Table Filling Algorithm. Lecture Notes. | Eleventh Lecture. Monday, 30 October 2023. Context-free grammars. Regular grammars have bound on derivation length that only depends on the length of the word, not the size of the grammar; context-free grammars do not. Trees: branching, levels, root, branch, the left-to-right order, subtree, labelling. Parse trees and their parsed string. Subtrees and substrings. Grafting. Equivalence of being derivable and being the string of a parse tree. Lecture Notes. | Twelfth Lecture. Wednesday, 1 November 2023. Chomsky Normal Form. Bound on derivation length based on word length; bound on word length based on parse tree height. Variable-targeted grammars, unit closed grammars. Transforming context-free grammars to variable-targeted and unit closed grammars. Chomsky's Theorem: each context-free grammar is equivalent to one in Chomsky Normal Form. Formulation of the context-free pumping lemma. Lecture Notes. |
| Week 5. | Thirteenth Lecture. Friday, 3 November 2023. Context-free pumping lemma (Bar-Hillel Lemma). Differences between the regular and the context-free pumping lemmas: location of the pump is not determined. There are languages that satisfy the context-free pumping lemma that are not context-free. Application: existence of a context-sensitive language that is not context-free. Proof of the context-free pumping lemma. Context-free languages are not closed under intersections, and therefore not under complements. The emptiness problem for context-free languages is solvable. Lecture Notes. | Fourteenth Lecture. Monday, 6 November 2023. Models of Computation and their storage. Brief mention of pushdown automata (no definition). Alan Turing, Turing machines, von Neumann architecture, development of register machines. Instructions, register machines, states, start state, halt state, program, program lines, upper register index, configuration or snapshot, register content. Register machines transforming configurations. Computation sequence, halting of a computation. Strong equivalence. There are only countably many register machines up to strong equivalence. Padding Lemma. Lecture Notes. | Fifteenth Lecture. Wednesday, 8 November 2023. Partial functions and notation for them: diverging and converging. Performing operations and answering questions. Examples. The subroutine lemma. The case distinction lemma. Many examples of performing operations and answering questions. Remark that constructions using operations and questions are precise definitions of concrete machines rather than informal descriptions. Lecture Notes. |
| Week 6. | Sixteenth Lecture. Friday, 10 November 2023. More examples of performing operations and answering questions. The partial function defined by a register machine. Computable partial functions. The identity, constant functions, and projections are computable. Characteristic and pseudocharacteristic functions. Computable and computably enumerable sets. A set is computable if any characteristic function is computable. Every computable set is computably enumerable. Lecture Notes. | Seventeenth Lecture. Monday, 13 November 2023. Notice of corrections of the typed notes: addition of the Repeat Lemma. The computable sets are closed under complement. Every regular language is computable. Example: \(\{a^nb^nc^n\,;\,n>0\}\) is computable. Relationship between Type 1, 2, and 3 languages and computable sets. The shortlex ordering and the successor function. The shortlex ordering is isomorphic to the natural numbers. The shortlex ordering and the successor function are computable. Church's recursive functions: basic functions, composition, and recursion. Lecture Notes. | Eighteenth Lecture. Wednesday, 15 November 2023. Examples of recursion operations on function: Grassmann recursion equations for addition, multiplication, and exponentiation. Composition and recursion preserve totality. Minimisation. Primitive recursive functions and recursive functions. Recursion trees. Assignment of functions to a recursion tree. Equivalence of being recursive and being the function assigned to a recursion tree. Every recursive function is computable. Proof of closure of the computable functions under recursion. Lecture Notes. |
| Week 7. | Nineteenth Lecture. Friday, 17 November 2023. Proof of closure of the computable functions under minimisation. Applications: arithmetical operations are computable. Cantor's zigzag function. Merging and splitting of words. Remark on the choice of alphabet (no details lectured). Coding of machines: numbers, states, instructions, program lines, register machines, sequences of words, configurations. All of the sets of codes are computable. The operation of transforming a configuration is computable. The truncated computation is computable. The software principle: statement and importance (no proof yet). Lecture Notes. | Twentieth Lecture. Monday, 20 November 2023. Proof of the Software Principle. Universal register machines. Notation \(f_{v,k}\) for the function computed by the register machine coded by \(v\). The \(s\)-\(m\)-\(n\) Theorem. Currying. The halting problem and its two-variable variant. The halting problem is c.e., but not computable. Notation \(\mathrm{W}_v := \mathrm{dom}(f_{v,1})\) for c.e. sets. \(\Sigma_1\), \(\Pi_1\), and \(\Delta_1\) sets. Projections. Computable sets are \(\Delta_1\) (no proof yet). Lecture Notes. | Twenty-first Lecture. Wednesday, 22 November 2023. Further explanations on the choice of alphabet: coding of \(\Sigma\)-register machines in \(\mathbb{W}\). Projections. Every computable set is \(\Delta_1\). Cylindres. Equivalence of being c.e. and being \(\Sigma_1\). Application: being type 0 is equivalent to being c.e. (proof only of the forward direction). The zigzag method: an example. Applications: being c.e. is equivalent to being the range of a computable function; being computable is equivalent to being \(\Delta_1\). Lecture Notes. |
| Week 8. | Twenty-second Lecture. Friday, 24 November 2023. Reminder of the goals of this lecture course: separation of Chomsky classes, closure properties, decision problems. Examples that separate all Chomsky classes from each other. Closure properties of the computable sets: union, intersection, concatenation, complement. Closure properties of the c.e. sets: intersection, union (zigzag method), concatenation (zigzag method). Overview of all closure properties (including those not proved in the course). What does it mean to give a negative solution to a decision problem: various formalisations of the informal notion of computation, e.g., Turing machines, register machines, recursive functions, WHILE programs. All of these coincide. The Church-Turing thesis. Definition of solvability. The word problem for type 0 grammars is unsolvable. Lecture Notes. | Twenty-third Lecture. Monday, 27 November 2023. Reduction function; many-one reducibility: reflexive, transitive, not anti-symmetric; many-one equivalence. Computability and being c.e. are preserved under many-one reducibility. Hardness and completeness. Remark on \(\mathbf{NP}\)-completeness. All computable sets (\(\neq \varnothing,\mathbb{W}\)) are \(\Delta_1\)-complete. The halting problem is \(\Sigma_1\)-complete. Degrees of unsolvability: picture of the lowest degrees. The Turing join (cf. Example Sheet #4). Index sets. Examples. The halting problem is not an index set (cf. Example Sheet #4, in particular the Recursion Theorem). Lecture Notes. | Twenty-fourth Lecture. Wednesday, 29 November 2023. Index sets as decision problems for grammars. Trivial index sets. Rice's Theorem. Consequences of Rice's Theorem for decision problems. Proof of Rice's Theorem. \(\mathbf{Fin}\) is neither \(\Sigma_1\) nor \(\Pi_1\). Summary of solvability of decision problems for grammars. Lecture Notes. |