 |
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. | Thursday, Saturday, Tuesday 11-12. | ||
| 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: 19 December 2022): pdf file. | ||
| L E C T U R E S. | |||
| Week 1. | First Lecture. Thursday, 6 October 2022. Computation & Computability. Existence vs algorithmic access to a witness. Examples: Hilbert's 10th problem and the Entscheidungsproblem. The objects of computation: strings of symbols. Countability, infinity, uncountability. The set of finite sequences from a countable set is countable. The power set of an infinite set is uncountable (Cantor's theorem). The set of finite subsets of a countable set is countable. Notations for strings: concatenation, iteration, recursive lifting of a function from a set to its set of finite sequences. Lecture Notes. Two excerpts from the typed lecture notes: Definitions, Proof of Cantor's Theorem. | Second Lecture. Saturday, 8 October 2022. Rewrite systems. There are only countably many rewrite systems for a fixed \(\Omega\). Rewriting in one step; rewriting in finitely many steps; derivations and their length. Relation to actual languages: human languages are finite, but exhibit linguistic recursion; Chomsky's grammatical and ungrammatical example sentences. Grammars: terminal and non-terminal symbols, alphabet, letters, words, variables, languages. There are uncountably many languages over each alphabet. Warm-up examples. Example: the language of odd-length words. Eight different grammars for the same language: notion of equivalence of grammars. Lecture Notes. Excerpts from the typed lecture notes: Proof that Chomsky's bad example is non-grammatical. | Third Lecture. Tuesday, 11 October 2022. Equivalent grammars. Isomorphisms. Isomorphic grammars are equivalent. The set of variables doesn't matter, only its size. Up to equivalence, there are only countably many languages produced by a grammar over a fixed alphabet \(\Sigma\). The Chomsky hierarchy: noncontracting, context-sensitive, context-free, regular. Types 0, 1, 2, & 3. Chomsky's Theorem: a language is noncontracting iff it is context-sensitive (without proof; cf. Example Sheet #1). Properness of the Chomsky hierarchy. Decision problems: the word problem, the emptiness problem, the equivalence problem. Solvability and unsolvability. Lecture Notes. Excerpts from the typed lecture notes: A non-context-free version of Chomsky's generative grammar. |
| Week 2. | Fourth Lecture. Thursday, 13 October 2022. A bound for the length of minimal derivations for noncontracting grammars. The word problem for noncontracting grammars is solvable. Closure properties: concatenation, union, intersection, complement, difference. Relations between closure properties. The concatenation grammar and the union grammar. Variable-based grammars. Every grammar is equivalent to a variable-based grammar. The concatenation and union grammar give concatenations and unions if the grammars are variable-based. The classes of context-free and context-sensitive languages are closed under concatenation; the classes of regular, context-free, and context-sensitive grammars are closed under union. [Note: the case of regular grammars needs a slightly different construction than the one given in the lectures. Cf. here: Union grammars for regular languages.] Remark on the empty word: languages that produce the empty word can be obtained by adding the basic \(\varepsilon\)-rule, but this requires that the grammars are \(\varepsilon\)-adequate. Every language is equivalent to a \(\varepsilon\)-adequate grammar. Lecture Notes. Excerpts from the typed lecture notes: Details of the proof that every grammar is equivalent to a variable-based grammar, Proof that for variable-based grammars, the concatenation grammar produces the concatenation, Proof that for variable-based grammars, the union grammar produces the union, Alternative construction of an \(\varepsilon\)-adequate equivalent grammar that preserves regularity. | Fifth Lecture. Saturday, 15 October 2022. Understanding regular derivations: what can be derived; what do derivations look like? An alternative concatenation construction: the class of regular languages is closed under concatenation. Deterministic automata, their graphical representation, and their computations: the recursively defined function \(\widehat{\delta}\), the language \(\mathcal{L}(D)\) accepted by an automaton \(D\), and the state sequence of the computation. Homomorphisms between automata. Homomorphic automata accept the same language (no proof). Lecture Notes. | Sixth Lecture. Tuesday, 18 October 2022. Proof that homomorphic automata accept the same language. Discussion of accessible and indistinguishable states. Every language accepted by a deterministic automaton is regular. Nondeterministic automata. Deterministic and nondeterministic automata accept the same languages: the subset construction. Every regular language is accepted by a nondeterministic automaton. Lecture Notes. |
| Week 3. | Seventh Lecture. Thursday, 20 October 2022. The pumping lemma and the pumping number. Application 1: \(\{0^k1^k\,;\,k>0\}\) is not regular. Proof of the pumping lemma. Application 2: \(\{0^nw\,;\,w\in\mathbb{W}\}\) is regular, but cannot have a deterministic automaton with \(\leq n\) states that accepts it. There are uncountably many languages that satisfy the pumping lemma; thus, there are non-regular languages that satisfy the pumping lemma. Closure properties: the class of regular languages is closed under complementation; thus, it is closed under intersection and difference. Product automata: alternative proof of closure under union and intersection. Lecture Notes. Excerpts from the typed lecture notes: Details of the construction of the automaton for complementation. | Eighth Lecture. Saturday, 22 October 2022. More applications of the pumping lemma: there are context-free languages that are not regular; the emptiness problem for regular languages is solvable. Regular expressions: language defined by a regular expression. Every regular expression defines a regular languages. Discussion of the converse (no proof). Lecture Notes. | Ninth Lecture. Tuesday, 25 October 2022. Reminder: homomorphisms between automata and conditions for their injectivity and surjectivity. Accessible and distinguishable states. Irreducible automata. Every homomorphism between irreducible automata is an isomorphism. Quotient automaton: proof of well-definition and that is has no indistinguishable states. Every automaton has an irreducible equivalent automaton. Equivalent irreducible automata are isomorphic. Uniqueness of the minimal automaton. There is an algorithm that checks whether states are inaccessible. Lecture Notes. |
| Week 4. | Tenth Lecture. Thursday, 27 October 2022. There is an algorithm that checks whether two states are indistinguishable: the Table Filling Algorithm. The equivalence problem for regular grammars is solvable. Context-free grammars: finitely branching trees; leaves, branches, subtrees, the left-to-right order. Lecture Notes. | Eleventh Lecture. Saturday, 29 October 2022. Parse trees. The string parsed by a parse tree. Derivative sequences of parse trees and their equivalence with derivations. Equivalent description of a context-free language in terms of existence of parse trees. Grafting of parse trees. Chomsky normal form. Length of derivations for grammars in Chomsky normal form. Lecture Notes. | Twelfth Lecture. Tuesday, 1 November 2022. Transformations of grammars: guaranteeing that all non-unary rules of variables on the right-hand side; unit closure; breaking up rules with right-hand side of length \(\geq 3\). Possibility of removing unit rules from any unit closed grammar without changing the language. Chomsky's theorem: every context-free grammar is equivalent to one in Chomsky normal form. The context-free pumping lemma: formulation and properties. The regular pumping lemma implies the context-free pumping lemma. Application: the language \(\{a^nb^nc^n\,;\,n>0\}\) is not context-free. Lecture Notes. |
| Week 5. | Thirteenth Lecture. Thursday, 3 November 2022. Parse trees for grammars in Chomsky normal form bound the length of their parsed word with respect to their height. The context-free pumping lemma and its proof. Closure properties: the class of context-free grammars is not closed under intersection, complementation, and difference. Decision problems: the emptiness problem for context-free grammars is solvable; the equivalence problem for context-free grammars is unsolvable (without proof). Lecture Notes. | Fourteenth Lecture. Saturday, 5 November 2022. Alan Turing and the description of computations. Register machines: registers, configurations, instructions, programs, program lines, upper register index. Transformation of a configuration by a register machine. Definition of the computation sequence of a register machine given an input. Halting, halting times, and halting register content. Strong equivalence of register machines. The padding lemma. Lecture Notes. | Fifteenth Lecture. Tuesday, 8 November 2022. There are only countably many register machines up to strong equivalence. Performing operations & answering questions: partial functions and their notation; performing an operation; examples; answering questions; examples. Concatenation lemma. Case distinction lemma. Examples of operations performed and questions answered by register machines. Lecture Notes. |
| Week 6. | Sixteenth Lecture. Thursday, 10 November 2022. More examples of operations performed and questions answered by register machines. Partial functions associated to register machines. Computable functions. Examples. Characteristic functions and the characteristic function. Computable sets. Lecture Notes. | Seventeenth Lecture. Saturday, 12 November 2022. Pseudocharacteristic functions and the pseudocharacteristic function. Computably enumerable sets. The computable sets are closed under complement. Every computable set is computably enumerable. Every regular language is computable. The shortlex order: isomorphism to the natural numbers. Addition and multiplication of words via shortlex. The successor function. The shortlex order and the successor function are computable. Lecture Notes. | Eighteenth Lecture. Tuesday, 15 November 2022. Church's recursive functions: basic functions, composition, recursion, and minimisation. The class of primitive recursive functions and the class of recursive functions. Addition, multiplication, and exponentiation via Grassmann's recursion equations. Recursion trees and primitive recursion trees. A function is (primitive) recursive if and only if there is a (primitive) recursion tree defining it. Lecture Notes. |
| Week 7. | Nineteenth Lecture. Thursday, 17 November 2022. Every partial recursive function is computable: closure of the computable functions under recursion and minimisation. Cantor's zigzag function: merging and splitting of words. Remark on the choice of the alphabet (no proofs): the notion of computability does not depend on the alphabet. Coding register machines and configurations. Operations performed and questions answered by register machines concerning encodings. The function producing codes of configurations is computable. The truncated computation function is computable. Universal register machines (no proof yet). Lecture Notes. Excerpt from the typed lecture notes: Section 4.6: Remark on the choice of the alphabet. | Twentieth Lecture. Saturday, 19 November 2022. Proof of the Software Principle. Universal register machines. Parametrisation of the class of computable functions and c.e. sets by words. The s-m-n Theorem. The halting problem: \(\mathbf{K}\) and \(\mathbf{K}_0\). The halting problem is c.e. The halting problem is not computable. \(\Sigma_1\) sets. Lecture Notes. | Twenty-first Lecture. Tuesday, 22 November 2022. \(\Pi_1\) and \(\Delta_1\) sets. Every computable set is \(\Delta_1\). A set is \(\Sigma_1\) if and only if it is computably enumerable. Applications: the zigzag technique. A set is \(\Delta_1\) if and only if it is computable. The set of computably enumerable sets is not closed under complementation. Every type 0 language is computably enumerable. Computable sets are closed under all five closure properties. Lecture Notes. |
| Week 8. | Twenty-second Lecture. Thursday, 24 November 2022. Computably enumerable sets are closed under intersection, union, and concatenation, but not under complementation and difference. Computably enumerable sets are ranges of partial computable functions. Turing machines and while programs. Equivalence of computability notions (without proof). Proof sketch of the fact that every computably enumerable language is a type 0 language. Formal definition of solvability of decision problems. Proof that the word problem for type 0 languages is not solvable. Lecture Notes. | Twenty-third Lecture. Saturday, 26 November 2022. Reduction functions and many-one reducibility. Partial preorders and the degrees of unsolvability. The degree of computable sets. The Turing join: construction of sets that are neither \(\Sigma_1\) nor \(\Pi_1\). Hardness and completeness. Excursion: polynomial-time functions, P, NP, the P vs NP problem, polynomial-time reducibility, NP-completeness. All nontrivial computable sets are \(\Delta_1\)-complete. The halting problem \(\mathbf{K}\) is \(\Sigma_1\)-complete. Lecture Notes. | Twenty-fourth Lecture. Tuesday, 29 November 2022. Index sets. Examples: trivial index sets, \(\mathbf{Emp}\), \(\mathbf{Fin}\), \(\mathbf{Inf}\), \(\mathbf{Tot}\). Rice's Theorem. The emptiness problem for type 0 grammars is unsolvable. The equivalence problem for type 0 grammars is unsolvable. \(\mathbf{Emp} \equiv_\mathrm{m} \mathbb{W}{\setminus}\mathbf{K}\) (cf. Example Sheet #4). \(\mathbf{Fin}\) is neither \(\Sigma_1\) nor \(\Pi_1\). Lecture Notes. |