INQ0091306 - AUTOMATA, LANGUAGES AND COMPUTATION 2023-2024
Topic outline
-
Content: Detailed description of course content and prerequisites can be found here.
Textbook: The adopted textbook is Introduction to Automata Theory, Languages and Computation (3rd Edition) by John E. Hopcroft, Rajeev Motwani and Jeffrey D. Ullman, Pearson New International Edition, 2007.
Additional resources: As a complement to the textbook, the course also uses a collection of exercises with solutions, and two electronic forums for discussion of technical and administrative information. You can also access video recordings of the lectures from past year at this link.
Logistics: Lectures are on Tuesday 12:30-14:00 (room Ae), Wednesday 12:30-14:00 (room Ce), and Friday 12:30am-14:00 (room Ae).
Office hours: Wednesday 10:30-12:00pm, email appointment required. Meetings can be in person or else on-line at this Zoom link.
-
Forum for general news and announcements. Only the lecturer can post in this forum. Subscription to this forum is automatic for every student who has registered to this course.
-
Forum for discussion of technical matter presented during the lectures. Any student with a unipd account can post in this forum. Subscription to this forum is automatic for every student who has registered to this course.
-
Collection of exercises with solutions, to be used to complement the textbook .
-
-
October 3rd, Tuesday (12:30-14:30)
Course administration and presentation
- Cours timetable
- Textbook & other material
- Content outline & final exam
- Statistics
Introduction to the theory of automata
- Examples of computational models
- Recognition models and generative models
- Proof techniques (to be revisited later)
- Basics of formal language theory: alphabet and strings
- String concatenations and its properties
References
- Hopcroft et al., chapter 1
-
October 4th, Wednesday (12:30-14:30)
Introduction to the theory of automata
- Notion of language
- Extensional and intensional specification of a language
- Set-formers
- Languages and decision problems (to be revisited later)
Finite state automata
- Deterministic finite state automata (DFA)
- String processing
- Mathematical definition of DFA
- Graphical representations for DFA
- Extended transition function
- Example
References
- Hopcroft et al., chapter 1
- Hopcroft et al., chapter 2
-
October 6th, Friday (12:30-14:30)
Finite state automata
- Example (continued)
- Language recognized by a DFA
- The class of regular languages
- Exercise
- Nondeterministic finite state automata (NFA): basic idea
- Interpretation by "independent" computations and interpretation by "oracle"
- Example of NFA
- Mathematical definition of NFA
- Extended transition function for NFA
References
- Hopcroft et al., chapter 2
-
October 10rd, Tuesday (12:30-14:30)
Finite state automata
- Language accepted by a NFA
- Examples
- Construction: Conversion of a NFA into a DFA through the subset construction
Exercises
- Define DFAs for the following three languages:
- \( L_1 = \{ w \; | \; w \in \{0,1\}^\ast,\) the pattern 011 occurs at least once within \( w \}\)
- \( L_2 = \{ w \; | \; w \in \{0,1\}^\ast,\) the pattern 011 does not occur within \( w \}\)
- \( L_3 = \{ w \; | \; w \in \{0,1\}^\ast,\) the pattern 011 occurs exactly once within \( w \}\)
References
- Hopcroft et al., chapter 2
-
October 11th, Wednesday (12:30-14:30)
Finite state automata
- Construction: Conversion of a NFA into a DFA through lazy evaluation
- Theorem: correctness of the subset construction
- Theorem: equivalence of DFA and NFA
- Theorem: Exponential growth of the set of states, worst case example
- Partial DFA
- Example on the subset construction for NFA
Exercises
- Let \(\#_a(w)\) be the number of occurrences of symbol \(a\) in string \(w\). Given two strings \(x\) and \(w\) over some alphabet \(\Sigma\), \(x\) is a prefix of \(w\) if we can write \(w = xv\) for some \(v \in \Sigma^\ast\). Define a DFA that accepts the language \( L = \{ w \; | \; w \in \{a,b\}^\ast, \) for every prefix \(x\) of \(w\) we have \( \#_b(x) \leq \#_a(x) \leq \#_b(x)+2 \} \) (exercise 2, 3rd question, final exam of 2019/09/13)
References
- Hopcroft et al., chapter 2
-
October 13th, Friday (12:30-14:30)
Finite state automata
- NFA with \(\varepsilon\)-transitions (\(\varepsilon\)-NFA): basic idea
- Definition of \(\varepsilon\)-NFA
- Definition of \(\varepsilon\)-closure
- Extension of the transition function
- Language accepted by an \(\varepsilon\)-NFA
- Conversion of an \(\varepsilon\)-NFA into a DFA: subset construction and \(\varepsilon\)-closure
- Theorem (proof omitted): Equivalence between \(\varepsilon\)-NFA and DFA
- Proof by mutual induction (Chapter 1, Section 1.4.4; Chapter 2, Exercise 2.9)
Research & application highlights
- Extensions of finite automata
- Applications
References
- Hopcroft et al., chapter 2
-
October 17th, Tuesday (12:30-14:30)
Regular expressions
- Set operators over languages
- Inductive definition of regular expression and of the generated language
- Examples
- Operator precedence
- Tree structure underlying a regular expression
- Translation of a DFA into a regular expression: state elimination construction
References
- Hopcroft et al., chapter 3
-
October 18th, Wednesday (12:30-14:30)
Regular expressions
- State elimination construction (continued)
- Example of the state elimination construction
- Translation of a regular expression into an \(\varepsilon\)-NFA
- Example
- Algebraic laws for regular expressions
Exercise
- Given two strings \(x\) and \(w\) over some alphabet \(\Sigma\), \(x\) is an infix of \(w\) if we can write \(w = uxv\) for \(u, v \in \Sigma^\ast\). We define \(\mathit{Infx}(w)\) as the set of all infixes of \(w\). For a language \(L\), we define \(\mathit{Infx}(L) = \{ x \mid w \in L, x \in \mathit{Infx}(w)\}\). Prove that if \(L\) is a regular language, then \(\mathit{Infx}(L)\) is also a regular language.
References
- Hopcroft et al., chapter 3
-
October 20th, Friday (12:30-14:30)
Properties of regular languages
- Intuitive idea underlying the pumping lemma for regular languages
- Theorem: pumping lemma for regular languages
Exercises
- Show that the language \( L_{eq} = \{ w \; | \; w \in \{0,1\}^\ast, \; \#_0(w) = \#_1(w) \} \) is not regular
- Show that the language \( L_{pr} = \{ 1^p \; | \; p \mbox{ prime} \} \) is not regular
- Show that the language \( \{ ww^R \; | \; w \in \{0,1\}^* \} \) is not regular, where \(R\) is the string reversal operator
References
- Hopcroft et al., chapter 4
-
October 24th, Tuesday (12:30-14:30)
Properties of regular languages
- Closure properties of regular languages: union, concatenation, Kleene star, language complementation
- Regular language intersection and intersection automaton
- Closure under set difference operator
- Closure under string reversal operator
Exercises
- Use structural induction to prove that if a regular expression \(R\) does not use the Kleen star operator \(\ast\), then \(L(R)\) is a finite language
- Use structural induction to define a construction that, given a regular expression \(R\), provides a regular expression \(P(R)\) generating the language of all prefixes of strings in \(L(R)\)
References
- Hopcroft et al., chapter 4
-
October 25th, Wednesday (12:30-14:30)
Properties of regular languages
- Test on the intersection between regular and non regular languages
- Superset and subset operators and language properties
Exercise
- Prove that the following languages are not regular (Exercise 1.6 in the Exercise collection):
- \( L_{=} = \{ a^{n} b^{n} \; | \; n \geq 1 \} \)
- \( L_{>} = \{ a^{n} b^{m} \; | \; n, m \geq 1, \; n > m \} \)
- \( L_{<} = \{ a^{n} b^{m} \; | \; n, m \geq 1, \; n < m \} \) <%7 % 6%>
- \( L_{\neq} = \{ a^{n} b^{m} \; | \; n,m \geq 1, \; n \neq m \} \)
References
- Hopcroft et al., chapter 4
-
October 27th, Friday (12:30-14:30)
Properties of regular languages
- Closure of regular languages under homomorphism application
- Time complexity for standard conversions
- Emptiness test for regular languages
- Membership test for regular languages
- Definition of equivalence for states of DFA
- Equivalence test on states for DFA
Research & application highlights
- Regular expressions
References
- Hopcroft et al., chapter 4
-
October 31st, Tuesday (12:30-14:30)
Properties of regular languages
- Equivalence of regular languages
- Minimization of DFAs
Exercises
- Let \(M\) be a DFA over alphabet \(\{0,1\}\) with initial state \(q_0\), final states \(q_2, q_3\) and transition function \(\delta(q_0,0) = q_1\), \(\delta(q_0,1) = q_0\), \(\delta(q_1,0) = q_2\), \(\delta(q_1,1) = q_3\), \(\delta(q_2,0) = q_0\), \(\delta(q_2,1) = q_0\), \(\delta(q_3,0) = q_3\), \(\delta(q_3,1) = q_0\). Convert \(M\) into a regular expression using the technique of state elimination (exercise from final exam of January 22nd, 2019)
- State whether the language \( L_1 = \{w \; | \; w \in \{a,b\}^*, \; \#_b(w) \leq \#_a(w) ≤ 2 \#_b(w) \} \) is a regular language
- State whether the language \( L_2 = \{w \; | \; w \in \{a,b\}^*, \; \#_a(w) \neq \#_b(w), \;  \#_a(w) \neq 2 \#_b(w) \} \) is a regular language
- Let \(\Sigma = \{a,b\}\) and let \(L = \{w w' \; | \; |w| = |w'|, w \neq w'\}\). Prove that \(L\) is not a regular language.
References
- Hopcroft et al., chapter 4
-
November 3rd, Friday (12:30-14:30)
Context-free grammars
- Introduction to context-free grammars (CFGs)
- Definition of CFG
- Rewrite relation, reflexive and transitive closure
- Derivation, leftmost derivation and rightmost derivation
- Language generated by a CFG
Exercises
- CFG for language \( L \) of all strings with balanced parentheses (assume \( \varepsilon \not \in L \))
References
- Hopcroft et al., chapter 5
-
November 7th, Tuesday (12:30-14:30)
Context-free grammars
- Sentential forms for a CFG
- Derivation composition and derivation factorisation
- Definition of parse tree
- Standard terminology for parse trees
- Relation between derivations, leftmost/rightmost derivations, and parse trees
- The relation between derivations and parse trees is not one-to-one
Exercises
- Write a CFG for the language \( L = \{ w \; | \; w = a^i b^j c^k, \; i, j, k \geq 1 \} \)
- Write a CFG for the language \( L = \{ w \; | \; w = a^i b^j c^k, \; \; i, j, k \geq 1, \; j \neq k \} \)
References
- Hopcroft et al., chapter 5
-
November 8th, Wednesday (12:30-14:30)
Context-free grammars
- Ambiguous CFGs
- Inherently ambiguous CFGs
- Transforming a regular expression into an equivalent CFG
- Transforming a FA into an equivalent CFG
Push-down automata
- Intuitive idea
- The stack auxiliary memory
- Move typologies for PDA
Exercises
- Show that the language \( L = \{ a^i b^j c^{i+j} \; | \; i,j \geq 1 \} \) is a CFL, by writing a CFG \(G\) such that \(L(G) = L\)
References
- Hopcroft et al., chapter 5
- Hopcroft et al., chapter 6
-
November 10th, Friday (12:30-14:30)
Push-down automata
- Definition of push-down automaton (PDA)
- Graphical representation of the transition function
- Instantaneous description and computation step
- Definition of computation for a PDA
- Examples
- Computational properties of PDAs
- Acceptance under final state and acceptance under empty stack
- Transformation of an empty stack PDA into a final state PDA and proof of correctness
- Transformation of a final state PDA into an empty stack PDA and proof of correctness
References
- Hopcroft et al., chapter 6
-
November 14th, Tuesday (12:30-14:30)
Push-down automata
- Transformation of a CFG into a PDA by simulation of leftmost derivations: main construction, no proof of correctness
- Transformation of a PDA into a CFG: statement only, no proof
Properties of context-free languages
- Elimination of useless symbols
- Algorithm for generating symbols
- Algorithm for reachable symbols
Exercises
- Specify a PDA recognising the language \( L = \{ a^i b^j c^{i+j} \; | \; i,j \geq 1 \} \). Informally explain the meaning of each state of the PDA
References
- Hopcroft et al., chapter 6
- Hopcroft et al., chapter 7
-
November 15th, Wednesday (12:30-14:30)
Properties of context-free languages
- Algorithm for nullable symbols
- Elimination of epsilon-productions
- Algorithm for unary pairs
- Elimination of unary productions
- CFG simplification
- Chomsky normal form
- Examples
Exercises
- Show that the language \( L = \{ w \; | \; w \in \{a,b\}^\ast, \#_a(w) \not = \#_b(w) \} \) is a CFL
References
- Hopcroft et al., chapter 7
-
November 17th, Friday (12:30-14:30)
Properties of context-free languages
- Lemma on parse trees in CNF
- Proof of pumping lemma for CFL
Exercises
- Let \( L = \{ a^nb^n \; | \; n \geq 1 \} \) and let \( L' = \{ a,b \}^+ \). State whether the the following three languages are regular: \( L \cdot L' \), \( L' \cdot L \), \( L' \cdot L \cdot L' \)
References
- Hopcroft et al., chapter 7
-
November 21st, Tuesday (12:30-14:30)
Properties of context-free languages
- Example of pumping lemma for CFL
- Properties of CFL that can be derived from the pumping lemma
- Closure of CFL under substitution
- Applications of the substitution theorem: closure of CFL under union, concatenation, Kleene closure, positive closure, and homomorphism
Research & application highlights:
- Context-free grammars
- Natural language processing
References
- Hopcroft et al., chapter 7
-
November 22nd, Wednesday (12:30-14:30)
Properties of context-free languages
- Closure of CFL under string reversal
- CFL and intersection
- Intersection between CFL and regular languages
- Other closure properties for CFL
- Computational analysis of transformations for CFG e PDA
- Emptyness for CFL
- Membership for CFL: the CKY algorithm
- Undecidable problems for CFL
References
- Hopcroft et al., chapter 7
-
November 24th, Friday (12:30-14:30)
Turing Machine
- General ideas about Turing Machine (TM)
- Mathematical definition of TM
- Instantaneous description of a TM
- Computation of a TM
- Example of computation of a TM
- Graphical representation of the transition function of a TM
- TM with output
- Language accepted by a TM
References
- Hopcroft et al., chapter 8
-
November 28th, Tuesday (12:30-14:30)
Turing Machine
- Language accepted by a TM
- Language accepted by a TM that always halts
- Recursive languages (REC) and recursively enumerable languages (RE)
- Decision problems and associated languages (see chapter 1, section 1.5.4)
- Decidable problems and recursive languages
- Programming techniques for TM
- State seen as a finite memory with random access
- Multiple tracks on the tape
Exercises
Prove the truth or falsehood of the following statements (exercise from final exam of February 13th, 2019)- Given a CFL \(L_1\) and given a language \(L_2\) in REG, the language \(L_1 \cap L_2\) can be in REG
- Given a CFL \(L_1\) and given a language \(L_2\) in REG, the language \(L_1 \cap L_2\) may not be in REG
- Given a CFL \(L_1\), each subset of \(L_1\) is still a CFL
- Given two languages \(L_1\) and \(L_2\) not in REG, the language \(L_1 \cup L_2\) cannot be in REG
References
- Hopcroft et al., chapter 8
- Hopcroft et al., chapter 1
-
November 29th, Wednesday (12:30-14:30)
Turing Machine
- Programming techniques for TM: examples
- Use of subroutines
- Extension of TM
- Multi-tape TM
Exercises
- State whether the following language is in CFL: \( L_1 = \{ a^n b a^n b a^m\; | \; n,m \geq 1, \; m \geq n \} \) (exercise 2 from final exam of February 13th, 2019)
- State whether the following language is in CFL: \( L_2 = \{ a^n b a^p b a^m\; | \; n,p,m \geq 1, \; m \geq n \} \) (exercise from final exam of February 13th, 2019)
References
- Hopcroft et al., chapter 8
-
December 1st, Friday (12:30-14:30)
Turing Machine
- Nondeterministic TM
- TM with restrictions
- TM with semi-infinite tape
- Multi-stack TM
- TM and modern computers
Exercises
- Minimization of DFA (exercise from final exam of February 13th, 2019)
References
- Hopcroft et al., chapter 8
-
December 6th, Wednesday (12:30-14:30)
Undecidability
- String indexing
- TM encoding and TM indexing
- The TM / string infinite table
Exercises
- Let \( \Sigma = \{ a, b, c \} \); consider the language \(L = \{ w \; | \; w \in \Sigma^\ast, \; \#_a(w) = \#_b(w) = \#_c(w) \}\). Show that \(L\) is not a CFL
- Assume \( \Sigma = \{ a, b, c \} \). State whether the following languages are regular or not (exercise from final exam of September 3rd, 2021)
- \( L_1 = \{ w \; | \; w = XuYvZ, \; X,Y,Z \in \Sigma, \; u,v \in \Sigma^\ast, \; X = Z, \; |u| = |v| \} \)
- \( L_2 = \{ w \; | \; w = XuYvZ, \; X,Y,Z \in \Sigma, \; u,v \in \Sigma^\ast, \; X = Y = Z \} \)
- \( L_3 = \{ w \; | \; w = XuYvZ, \; X,Y,Z \in \Sigma, \; u,v \in \Sigma^\ast, \; X = Y = Z, \; |u| = |v| \} \)
References
- Hopcroft et al., chapter 9
-
December 12th, Tuesday (12:30-14:30)
Undecidability
- Diagonalization language \( L_d \)
- Properties of recursive languages
- Properties of RE languages
- Universal Language \( L_u \)
- Universal TM \( U \)
- \( L_u \) is in RE
- \( L_u \) is not in REC (\(L_d \leq_m \overline{L_u}\))
- Halting problem for a TM on a given input
References
- Hopcroft et al., chapter 9
-
December 15th, Friday (12:30-14:30)
Undecidability
- Notion of reduction between two decision problems
- Properties of reduction
- Definition of languages \( L_{e} \) and \( L_{ne} \)
- \( L_{ne} \) is in RE
Exercises
- Let \( \Sigma = \{a,b\} \). State whether the following languages are regular
(first three questions are from final exam of June 28th, 2019)
- \(L_1 = \{ bbxbbx^R \; | \; x \in \Sigma^\ast \}\)
- \(L_2 = \{ bbx \; | \; x \in \Sigma^\ast \} \cdot \{ bbx^R | x \in \Sigma^\ast \} \)
- \( L_3 = \{ bbx \; | \; x \in \Sigma^\ast \} \cdot L_1 \cdot \{ bbx^R \; | \; x \in \Sigma^\ast \}\)
- \( L_4 = \{ x \; | \; x \in \Sigma^\ast \} \cdot \{ xx^R \; | \; x \in \Sigma^\ast \} \cdot \{ x^R \; | \; x \in \Sigma^\ast \}\)
References
- Hopcroft et al., chapter 9
-
December 19th, Tuesday (12:30-14:30)
Undecidability
- \( L_{ne} \) is not in REC (\(L_u \leq_m L_{ne}\))
- \( L_{e} \) is not in RE
Exercises
- Let \( G \) be the CFG with productions \(S \rightarrow AC\), \(A \rightarrow BA \; | \; a\), \(B \rightarrow b\), \(C \rightarrow BC \; | \; c\). Apply the CYK agorithm to the string \( w = bbabbbc \) (exercise from final exam of June 28th, 2019)
- Answer to the following yes/no questions, providing a motivation (exercise from final exam of June 28th, 2019)
- Is REC closed under intersection?
- Is RE closed under intersection?
- If \( L_1 \) is in REC and \( L_2 \) is in RE, is \( L_1 \cap L_2 \) always in REC?
- If \( L_1 \) is in REC and \( L_2 \) is in RE, is \( L_1 \cap L_2 \) always outside of REC?
- Let \( r = (ab+aab)^\ast \). Convert \(r\) into an equivalent \(\varepsilon\)-NFA (exercise from final exam of June 28th, 2019)
Refereces
- Hopcroft et al., cap. 9
-
December 20th, Wednesday (12:30-14:30)
Undecidability
- Properties \( \cal P\) of RE languages and associated languages \( L_\cal P\)
- Rice's theorem
- Discussion
- Definition of Post's correspondence probem (PCP)
- Example
- PCP is not recursive (no proof)
Exercises
-
Let \(\Sigma = \{a,b\}\). State whether the following languages are regular (final exam of September 19th, 2022)
- \( L_1 = \{ w \; | \; w = a^pba^q, \; p,q \geq 0, \; 1 \leq p + q \} \)
- \( L_2 = \{ w \; | \; w = a^pba^q, \; p,q \geq 0, \; 1 \leq p - q \} \)
- \( L_3 = \{ w \; | \; w = a^pba^q, \; p,q \geq 0, \; p = q^3 \mbox{ or } q = p^3 \} \)
References
- Hopcroft et al., chapter 9
-
December 22th, Friday (12:30-14:30)
Undecidability
- Definition of the ambiguity problem for CFL and the associated language \(L_{\mathit{AMB}}\)
- Reduction from PCP to \(L_{\mathit{AMB}}\)
Exercises
- Let \(L_{ev}\) be the language of all strings in \(\{0,1\}^\ast\) with even length. Define \({\cal P} = \{ L \; | \; L \in {\rm RE}, \; L_{ev} \subsetneq L \} \) and define \( L_{\cal P} = \{ \mathsf{enc}(M) \; | \; L(M) \in {\cal P} \} \). Is \(L_{\cal P}\) a recursive language? (exercise from final exam of January 22nd, 2019)
- Let \(L_1\) and \(L_2\) be recursive languages. Is \(L_1 L_2\) a recursive language? (exercise from final exam of January 22nd, 2019)
- Let \(L = \{ enc(M_1, M_2) \; | \; L(M_1) \subseteq L(M_2) \} \) with \(M_1, M_2\) TMs. Is \(L\) a recursively enumerable language? (exercise from final exam of January 22nd, 2019)
References
- Hopcroft et al., chapter 9
-
January 9th, Tuesday (12:30-14:30)
Intractability
- Intractable problems
- Time complexity for a TM
- Polynomial time algorithms
- Complexity analysis for a TM
- Nondeterministic polynomial time algorithms
- Polynomial time reduction
- NP-complete problems and NP-hard problems
Exercises
Prove the truth or falsehood of the following statements (exercise from final exam of January 27th, 2020)- Given \(L_1\) and \(L_2\) not in REG, the language \(L_1 \cap L_2\) cannot be in REG
- Given \(L_1\) in REG and \(L_2\) in CFL, the language \(L_1 L_2\) is in REG
- Given \(L_1\) in CFL, the language \(\overline{L_1}\) cannot be in CFL
- Given \(L_1\) and \(L_2\) in CFL, the language \(L_1 \cap L_2\) is in REC
References
- Hopcroft et al., chapter 10
-
January 10th, Wednesday (12:30-14:30)
Intractability
- Boolean expressions
- Satisfiability of Boolean expressions and the SAT problem
- Coding for Boolean expressions
- Cook's theorem (proof of first part only)
- Normal forms for Boolean expressions
- CSAT problem and 3SAT problem
- Definition of independent set and the IS problem
- The problem IS is NP-complete
Exercises
- Let \(w\) be a string in \(\{0,1\}^\ast\). Define \({\cal P} = \{ L \; | \; L \in {\rm RE}, \; w \in L \} \) and define \( L_{\cal P} = \{ \mathsf{enc}(M) \; | \; L(M) \in {\cal P} \} \). Is \(L_{\cal P}\) a recursive language? Is \(L_{\cal P}\) a recursively enumerable language? (exercise from final exam of February 13th, 2019)
References
- Hopcroft et al., cap. 10
-
January 10th, Wednesday (14:30-16:30)
Exercises
- Recall that for two strings \( x,w \in \Sigma^\ast \), we say that \(x\) is an infix of \(w\) if we can write \(w = uxv\) for some strings \( u,v \in \Sigma^\ast \). Define \({\cal P} = \{ L \; | \; L \in {\rm RE},\) every string in \( L \) has infix \( 01110\}\) and define \( L_{\cal P} = \{ \mathsf{enc}(M) \; | \; L(M) \in {\cal P} \} \).
- Use Rice's theorem to show that \(L_{\cal P}\) is not a recursive language
- Prove that \(L_{\cal P}\) is not in RE
- For a language \(L\) over \(\Sigma\), let \({\sf pref}(L) = \{ w \; | \; wx \in L, \; w \in \Sigma^\ast, \; x \in \Sigma^+ \}\). State whether RE is closed under the operator \({\sf pref}\) (exercise 3.7 from the Exercise collection)
- Assess whether the following languages are in RE (exercise from final exam of September 13th, 2019):
- \(L_1 = \{ enc(M, M') \; | \; L(M) \cup L(M') = \emptyset \}\)
- \(L_2 = \{ enc(M, M') \; | \; L(M) \cup L(M') \neq \emptyset \}\)
- Recall that for two strings \( x,w \in \Sigma^\ast \), we say that \(x\) is an infix of \(w\) if we can write \(w = uxv\) for some strings \( u,v \in \Sigma^\ast \). Define \({\cal P} = \{ L \; | \; L \in {\rm RE},\) every string in \( L \) has infix \( 01110\}\) and define \( L_{\cal P} = \{ \mathsf{enc}(M) \; | \; L(M) \in {\cal P} \} \).
-
January 12th, Friday (12:30-14:30)
Intractability
- The problem IS is NP-complete
- Definition of node cover and the NC problem
- NC is NP-complete
- Definition of a directed Hamiltonian circuit and the DHC probem
- DHC is NP-complete
- HC is NP-complete
- TSP is NP-complete
Exercises
- Let \( \Sigma = \{a,b,c\} \). State whether the languages \( L_1 = \{ a^n a^m b^n c^m \; | \; n, m \geq 1 \} \) and \( L_2 = \{ a^n a^n b^n c^n \; | \; n \geq 1 \} \) are context-free (exercise from final exam of June 28th, 2021)
- Let \( L_1 \) be a finite language defined over \( \Sigma = \{0,1\} \). Define \( {\cal P} = \{ L \; | \; L \in {\rm RE}, \; L_1 \cap L \not = \emptyset \}\). State whether \(L_{\cal P}\) is in REC, in RE but not in REC, or else outside of RE (exercise 3.8 from the Exercise collection)
- Let \( L_R \) be a regular language defined over \( \Sigma \), and let \( {\cal P} = \{ L \; | \; L \in {\rm RE}, \; L \cup L_R \not = \Sigma^\ast \}\). State whether the languages \( L_1 = L_{{\cal P}} \) and \( L_2 = \{ enc(M_1, M_2) \; | \; L(M_1) \cup L(M_2) \cup L_R = \Sigma^\ast \} \) belong to REC (exercise from final exam of June 28th, 2021)
- Let \(\Sigma = \{a,b\}\). Assess whether the following languages are CFL (exercise from final exam of January 27th, 2020):
- \( L_1 = \{ xyx^Ry^R \; | \; x,y \in \Sigma^+ \} \)
- \( L_2 = \{ xyy^Rx^R \; | \; x,y \in \Sigma^+ \} \)
- \( L_3 = \{ xyy^Rx^R \; | \; x,y \in \Sigma^+, \; |x| = |y| \} \)
- Hopcroft et al., chapter 10
References
-
The course syllabus is based on the adopted textbook: Introduction to Automata Theory, Languages and Computation (3rd Edition) by John E. Hopcroft, Rajeev Motwani and Jeffrey D. Ullman, Pearson New International Edition, 2007. Some topics explicitly marked in the syllabus must be supplemented with lecture slides, available on the course website.
-
The videos in this box were recorded in the academic year 2021-22 upon the request of some students. They contain overview of the standard questions that are asked at the final exams.
-
What follows are the final exams from the past academic year, in some cases with solutions.
-
In this box you can find some of the resources that have been produced for the student coaching program of Summer 2023. This includes video recordings and slides used during the sessions, as well as all homework assignments.
This auxiliary material is meant for students who have not been able to attend the main lectures: if you are not in this category, you do not need to look into these videos.