Class

Here is the detailed list of subjects from Chapter 1 that we have presented in class and that will be matter of evaluation at the finals.

Chapter 1: Automata: The Methods and the Madness.

Recognition models and generative models (lecture slides). Introduction to proof techniques: deductive proofs and the if-then form, proof by counterexample, proof of equality of two sets (lecture slides). Notions of alphabet and string. The concatenation operation and the empty string. Extensional and intensional definition of language. The use of set-former.

Skip: Sections 1.1, 1.2, 1.3, 1.4.

Here is the detailed list of subjects from Chapter 3 that we have presented in class and that will be matter of evaluation at the finals.

Chapter 3: Regular Expressions and Languages.

Set operations on languages. Regular expression operators. Inductive definition of regular expression and of the generated language. Operator's precedence. Conversion of a DFA into a regular expression: construction by state elimination. Conversion of a regular expression into an eps-NFA. Algebraic laws for regular expressions: commutativity and associativity, identity and annihilators, distributivity and idempotency. Kleene closure and its properties.

Skip: Sections 3.2.1, 3.3, 3.4.6, 3.4.7.

Here is the detailed list of subjects from Chapter 4 that we have presented in class and that will be matter of evaluation at the finals.

Chapter 4: Properties of regular languages.

Pumping lemma for regular languages and applications. Closure properties for regular languages and associated proofs: union, concatenation, Kleene star, complementation, intersection (including construction of the intersection automaton), set difference, string reverse, homomorphism. Computational complexity of the studied conversions (main results only, skip proofs). Decision problems for regular languages (algorithms only, skip proofs): test for emptiness; membership test; definition of equivalent states and state equivalence algorithm; equivalence test for regular languages. DFA minimization (algorithm only, skip proof).

Skip: Sections 4.2.4, 4.4.4; all proofs from Section 4.3.1; Theorem 4.20; time complexity of the state equivalence algorithm; Theorems 4.23 and 4.24.

Here is the detailed list of subjects from Chapter 5 that we have presented in class and that will be matter of evaluation at the finals.

Chapter 5: Context-free grammars and languages.

Basic idea. Definition of context-free grammar (CFG). Basic notions: rewrite relation, derivation, leftmost and rightmost derivation, generated language. Notion of sentential form. Properties of derivations: derivation composition and derivation factorisation. Parse tree and its yield. Equivalence between derivations, leftmost/rightmost derivations, and parse trees (skip the proofs). Grammar ambiguity. One-to-many correspondence between derivations and parse trees. One-to-one correspondence between leftmost derivations and parse trees. Inherent ambiguity. Transformation from FA to CFG and transformation from regular expression to CFG (lecture slides).

Skip: Theorem 5.7; notion of recursive inference and Example 5.4; proofs of Theorems 5.12, 5.14, 5.18; Sections 5.3 and 5.4.2; proof of Theorem 5.29.

Here is the detailed list of subjects from Chapter 6 that we have presented in class and that will be matter of evaluation at the finals.

Chapter 6: Push-down automata.

Basic idea. Definition of push-down automaton (PDA). Graphical representation for the transition function of a PDA. Definitions of instantaneous description and of computation for a PDA. Properties of the computations of a PDA: removal or addition of string/stack portions that are never used in the computation. Acceptance by final state and acceptance by empty stack. Equivalence between PDA with acceptance by final state and PDA with acceptance by empty stack. Transformation from CFG to PDA: main idea and construction, skip proof. Transformation from PDA to CFG: statement only, skip proof.

Skip: proof of Theorem 6.5; Examples 6.7, 6.8 and 6.10; proof of Theorem 6.13 and proof of Theorem 6.14; Section 6.4.

Here is the detailed list of subjects from Chapter 7 that we have presented in class and that will be matter of evaluation at the finals.

Chapter 7: Properties of context-free languages.

Definition of generating symbols and reachable symbols and algorithms for their recognition. Definition of useless symbols and algorithm for their elimination in a CFG. Definition of nullable symbols and algorithm for their recognition. Algorithm for the elimination of epsilon-productions in a CFG. Notion of unit pair in a CFG and algorithm for their recognition. Algorithm for the elimination of unit productions in a CFG. Simplification of a CFG. Definition of Chomsky normal form (CNF) and algorithm for casting a CFG in CNF. Pumping lemma for CFL and its application. Properties of context-free languages derived from the pumping lemma. Closure properties of context-free languages: substitution, union, concatenation, Kleene closure and positive closure (operator +), homomorphism. Other closure properties for context-free languages: reverse operator, intersection with regular languages and construction of the corresponding PDA, set difference with regular languages. Context-free languages are not closed with respect to intersection, complement and set difference. Computational complexity of conversions, including CNF conversion. Test for emptiness for CFL (informal description). Algorithm for the membership problem for CFL (CYK algorithm). Preview of undecidable problems for CFL.

Skip: proofs of all theorems for CFG simplification and for CNF construction: Theorems 7.2, 7.4, 7.6, 7.7, 7.9, 7.11, 7.13, 7.14 and 7.16; Exercise 7.28; Section 7.3.5; proofs of Theorems 7.31 and 7.32; linear time algorithm in Section 7.4.3.

Here is the detailed list of subjects from Chapter 8 that we have presented in class and that will be matter of evaluation at the finals.

Chapter 8: Turing Machines: Introduction.

Definition of Turing Machine (TM) and transition diagram. Notions of instantaneous description, computation step and computation for a TM. TM with output. Language accepted by a TM upon final state and the class of recursively enumerable languages (RE). The halting problem for TM. The class of recursive languages (REC). Programming techniques for TM: finite random access memory embedded in states; multiple tracks; subroutine call and return address. Extensions of TM: multi-tape TM and equivalence with TM, computation time; non-deterministic TM and equivalence with TM, computation time. Restrictions of TM: semi-infinite tape without blank writing and equivalence with TM (sketch of proof as in slides); multi-stack machines and equivalence with TM (statement only, no proof). Equivalence of TM and modern computer (statement only, no proof).

Skip: Sections 8.1, 8.5.3, 8.5.4, 8.6; proof of Theorem 8.12 only in the simplified form presented in the slides (no detailed specification of the transition function); proof of Theorem 8.13.

Here is the detailed list of subjects from Chapter 9 that we have presented in class and that will be matter of evaluation at the finals.

Chapter 9: Undecidability.

Indexing for binary strings and indexing for TMs. Recursive languages (REC) and recursively enumerable languages (RE). Definition of the diagonalization language. The diagonalization language is not in RE. Definition of the universal language. The universal language is in RE. The universal language is not in REC. Definition of reduction. The language of all TM encodings that accept a non-empty language is in RE but not in REC. The language of all TM encodings that accept the empty language is not in RE. Rice's theorem and its applications. Definition of the Post correspondence problem (PCP). PCP is not in REC (no proof).

Skip: Proofs of Theorems 9.17 and 9.19; Section 9.5.

Here is the detailed list of subjects from Chapter 10 that we have presented in class and that will be matter of evaluation at the finals.

Chapter 10: Intractable problems.

Computational complexity of a TM. Definition of the class deterministic polynomial time (P) and the class non-deterministic polynomial time (NP). Polynomial time reductions. NP-complete problems and NP-hard problems. Boolean expressions and their encoding. Satisfiability of Boolean expressions and the SAT problem. Cook theorem: SAT is NP-complete (first part of the proof only: SAT is in NP). Normal forms for Boolean expressions. CSAT and 3SAT are NP-complete (statement only, no proof). Definitions of independent sets and of the IS problem. IS is NP-complete. Definitions of node cover and of the NC problem. NC is NP-complete (statement only, no proof). Definitions of directed Hamiltonian circuit and of the DHC problem. DHC is NP-complete (statement only, no proof). Other NP-complete problems.

Skip: Second part of the proof of Theorem 10.9; Sections 10.3.2, 10.3.3, and 10.3.4; proofs of Theorems 10.21, 10.23, and 10.24.