INQ0091306  AUTOMATA, LANGUAGES AND COMPUTATION 20232024
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:3014:00 (room Ae), Wednesday 12:3014:00 (room Ce), and Friday 12:30am14:00 (room Ae).
Office hours: Wednesday 10:3012:00pm, email appointment required. Meetings can be in person or else online 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:3014: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:3014:30)
Introduction to the theory of automata
 Notion of language
 Extensional and intensional specification of a language
 Setformers
 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:3014: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:3014: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:3014: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:3014: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:3014: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:3014: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:3014: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:3014: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:3014: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:3014: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:3014: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:3014:30)
Contextfree grammars
 Introduction to contextfree 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:3014:30)
Contextfree 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 onetoone
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:3014:30)
Contextfree grammars
 Ambiguous CFGs
 Inherently ambiguous CFGs
 Transforming a regular expression into an equivalent CFG
 Transforming a FA into an equivalent CFG
Pushdown 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:3014:30)
Pushdown automata
 Definition of pushdown 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:3014:30)
Pushdown 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 contextfree 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:3014:30)
Properties of contextfree languages
 Algorithm for nullable symbols
 Elimination of epsilonproductions
 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:3014:30)
Properties of contextfree 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:3014:30)
Properties of contextfree 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:
 Contextfree grammars
 Natural language processing
References
 Hopcroft et al., chapter 7

November 22nd, Wednesday (12:3014:30)
Properties of contextfree 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:3014: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:3014: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:3014:30)
Turing Machine
 Programming techniques for TM: examples
 Use of subroutines
 Extension of TM
 Multitape 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:3014:30)
Turing Machine
 Nondeterministic TM
 TM with restrictions
 TM with semiinfinite tape
 Multistack 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:3014: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:3014: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:3014: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:3014: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:3014: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:3014: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:3014:30)
Intractability
 Intractable problems
 Time complexity for a TM
 Polynomial time algorithms
 Complexity analysis for a TM
 Nondeterministic polynomial time algorithms
 Polynomial time reduction
 NPcomplete problems and NPhard 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:3014: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 NPcomplete
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:3016: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:3014:30)
Intractability
 The problem IS is NPcomplete
 Definition of node cover and the NC problem
 NC is NPcomplete
 Definition of a directed Hamiltonian circuit and the DHC probem
 DHC is NPcomplete
 HC is NPcomplete
 TSP is NPcomplete
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 contextfree (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.

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.