Exercises for the continuous assessment
This page contains a list of exercises on the topics covered in the course.
The exercises are grouped into Homeworks (HW). On the racó roughly every other week you’ll be assigned an exercise from a homework (or part of an exercise). Consult the racó to see what exercise was assigned to you and prepare to present your solution at the blackboard.
You are encouraged to discuss your solutions with other students and work in groups (especially with students having assigned parts of the same exercise). In class, though, the presentations at the blackboard are individual.
On notation
In the exercises below we use common standard mathematical notation and some slightly non-standard one:
\lambda denotes the empty string. In most books this is denoted as \epsilon: this is the case for instance of (Sipser 2013), (Hopcroft, Motwani, and Ullman 2007), and (Kozen 1997).1
given n\in \mathbb N, we use n\mathbb N or \dot n to denote the set of nonnegative multiples of n. Writing m\in n\mathbb N +k is the same as stating that m\equiv k \pmod{n}. For instance, it is true that 6\in 3\mathbb N and 16\in 5\mathbb N +1, while 13\notin 7\mathbb N.
for a binary string w, \mathtt{value}_2(w) denotes the binary value of the string w. By convention, \mathtt{value}_2(\lambda)=0. Observe that \mathtt{value}_2(w0)=2\cdot\mathtt{value}_2(w) and \mathtt{value}_2(w1)=2\cdot\mathtt{value}_2(w)+1. Also notice that an arbitrary number of leading zeros in a string gives rise to the same number: \mathtt{value}_2(w)=\mathtt{value}_2(0w)=\mathtt{value}_2(00w)=\mathtt{value}_2(000w)=\cdots. In particular, for every natural number n there are infinite binary words w such that \mathtt{value}_2(w)=k.
Homework 1
Resources useful to solve the exercises in this problem set are the following:
Guille Godoy’s video lectures
Books
- (Sipser 2013, \S 0)
- (Cases and Màrquez 2003, \S 1)
- (Hopcroft, Motwani, and Ullman 2007, \S 1)
In the following exercises you can assume all well-known basic properties of union, intersection, and complement of sets. For example the distributivity of intersection over union, the distributivity of union over intersection, and de Morgan’s laws, i.e. given sets A,B,C it holds that
- A\cap (B\cup C)=(A\cap B)\cup (A\cap C) and A\cup (B\cap C)=(A\cap B)\cup(A\cup C),
- \overline{A\cap B}=\overline A\cup \overline B and \overline{A\cup B}=\overline A\cap \overline B.
Recall also that to show an equality betwen two sets A and B, it is enough to show that A\subseteq B and B\subseteq A, that is for every x\in A it holds that x\in B and, viceversa, that for every y\in B it holds that y\in A.
| # | Title | Categories |
|---|---|---|
| 1 | From informal to formal descriptions | theory of languages |
| 2 | Concatenation – basic properties | theory of languages, concatenation |
| 3 | Kleene Star – basic properties | Kleene star, theory of languages |
| 4 | Characterizations | Kleene star, theory of languages |
| 5 | Reverse – basic properties | theory of languages, reverse |
| 6 | Homomorphisms I – basic properties | homomorphism, theory of languages |
| 7 | Homomorphisms II – basic properties | homomorphism, theory of languages |
| 8 | On the size of languages | theory of languages, cardinality of languages |
| 9 | Shifting a language | theory of languages, shift |
| 10 | Simplification of languages | theory of languages |
| 11 | L=\overline{\Sigma L} | theory of languages, hard exercise |
| 12 | Arbitrary long walks in graphs | pigeonhole principle |
| 13 | Easy induction | induction proof |
| 14 | Divisibility in number set | induction proof, proof by cases, hard exercise, pigeonhole principle |
Homework 2
Resources useful to solve the exercises in this problem set are the following:
Guille Godoy’s video lectures
Books
- Exemples de construcció d’autòmats finits (Lluís Màrquez, Enrique Romero)
- (Cases and Màrquez 2003, \S 4 and \S 5)
- (Sipser 2013, \S 1.1 and \S 1.2)
- (Hopcroft, Motwani, and Ullman 2007, \S 2.1, \S 2.2 and \S 4.2)
| # | Title | Categories |
|---|---|---|
| 1 | Union and intersection of regular languages – the product construction | regular languages, union, intersection, product construction, minimization of DFAs |
| 2 | Complement of a regular language is regular | regular languages, complement, minimization of DFAs |
| 3 | Concatenation of regular languages is regular | regular languages, concatenation, minimization of DFAs |
| 4 | Kleene star of a regular language is regular | regular languages, Kleene star, minimization of DFAs |
| 5 | Reverse of a regular language is regular | regular languages, reverse |
| 6 | Homomorphism of a regular language is regular | regular languages, homomorphism, minimization of DFAs |
| 7 | Inverse homomorphism of a regular language is regular | regular languages, homomorphism, minimization of DFAs |
| 8 | On DFA minimization | regular languages, minimization of DFAs |
| 9 | NFAs can be exponentially more succinct than DFAs | regular languages, NFAs vs DFAs, pigeonhole principle, minimization of DFAs |
| 10 | DFAs – some decidable properties | regular languages, decidable properties |
| 11 | Finite languages are regular | regular languages, union, finite set |
| 12 | Membership in a regular language is decidable in polynomial time | regular languages, polynomial time, membership problem |
| 13 | Arithmetic progressions are regular | regular languages, arithmetic progressions, hard exercise, base-2, unary |
| 14 | At least k occurrences of every symbol is a regular language | regular languages, minimization of DFAs, pigeonhole principle, hard exercise |
| 15 | First half of regular is regular | regular languages, first half, hard exercise |
| 16 | IntercalAND of regulars is regular | regular languages, intercalAND |
| 17 | Prefixes and suffixes | regular languages, prefixes, suffixes |
Homework 3
Resources useful to solve the exercises in this problem set are the following:
Guille Godoy’s video lectures
Books
- (Sipser 2013, \S 1.4 Nonregular Languages)
- (Cases and Màrquez 2003, \S 7.1)
- (Sipser 2013, \S 1.3 Regular Expressions)
- (Cases and Màrquez 2003, \S 6.1 – \S 6.4)
- (Hopcroft, Motwani, and Ullman 2007, \S 4.1 and \S 3)
| # | Title | Categories |
|---|---|---|
| 1 | Variations on a^n b^n | pumping lemma, dyck language |
| 2 | Counting as and bs is (in general) not regular | pumping lemma |
| 3 | On as in the first part and bs in the second part | pumping lemma, hard exercise |
| 4 | Palindromes and partial palindromes | pumping lemma, hard exercise |
| 5 | Checking basic arithmetic is not regular | pumping lemma |
| 6 | Unary sequences with arbitrarily large gaps | pumping lemma |
| 7 | Approximations of real numbers | pumping lemma, diagonalization, hard exercise |
| 8 | What operations preserve non-regularity? | non regularity, union, complement, intersection, reverse, shift, Kleene star, homomorphism, inverse homomorphism |
| 9 | Arden’s Lemma and applications | theory of languages, Arden’s Lemma, hard exercise, regular expressions |
| 10 | Regular expressions and closure properties of regular languages | regular expressions, union, complement, intersection, reverse, homomorphism, inverse homomorphism, Kleene star, concatenation |
| 11 | On some decidable properties of regular expressions | regular expressions, decidable properties |
| 12 | Transformation of regular expressions | regular expressions |
Homework 4
Resources useful to solve the exercises in this problem set are the following:
Guille Godoy’s video lectures
Books
- (Sipser 2013, \S 2.1 Content-free Grammars)
- (Cases and Màrquez 2003, \S 2 and \S 3)
- (Hopcroft, Motwani, and Ullman 2007, \S 5)
| # | Title | Categories |
|---|---|---|
| 1 | Just context-free, or actually regular? | context-free languages, pumping lemma |
| 2 | Ambiguous context-free grammars | ambiguity, context-free languages |
| 3 | On Dyck languages | context-free languages, ambiguity, dyck language |
| 4 | Context-free closure operations and ambiguity | context-free languages, ambiguity, union, concatenation, reverse, Kleene star, homomorphism |
| 5 | Depuration of grammars | context-free languages, depuration of grammars |
| 6 | On the Chomsky normal form | Chomsky normal form, context-free languages |
| 7 | Membership in a context-free language is decidable in polynomial time | membership problem, context-free languages, CKY algorithm, decidable properties |
| 8 | Some decidable properties of context-free languages | decidable properties, context-free languages |
| 9 | Complement of context-free sometimes is context-free | complement, context-free languages, hard exercise |
| 10 | Sufficient conditions for unambiguity | context-free languages, ambiguity |
| 11 | On regular grammars | context-free languages, depuration of grammars, regular languages, linear grammar, regular grammar, ambiguity |
Homework 5
Resources useful to solve the exercises in this problem set are the following:
Guille Godoy’s video lectures
Books
- (Sipser 2013, \S 3 and \S 4.1)
- (Hopcroft, Motwani, and Ullman 2007, \S 8)
- (Kozen 1997, Lectures 28-32)
- (Serna et al. 2004, \S 1, 2, 3)
The following exercises use common notation in computability, in particular:
- \mathbf{R} is the set of all decidable (aka recursive) languages.
- \mathbf{RE} is the set of all semi-decidable (aka recursively enumerable) languages.
- \mathbf{coRE} the set of all languages L such that \overline L\in \mathbf{RE}. \mathbf{coRE} is not the complement of \mathbf{RE}. Indeed most of the languages are neither in \mathbf{RE} nor in \mathbf{coRE}.
Recall that \mathbf{R}=\mathbf{RE}\cap \mathbf{coRE}.
| # | Title | Categories |
|---|---|---|
| 1 | Turing machines for simple languages | Turing machines |
| 2 | Equivalent models of Turing machines | Turing machines |
| 3 | \mathbf{R}, \mathbf{RE}, and \mathbf{coRE} are closed under union, intersection, and reverse | R (decidable/recursive languages), RE (semi-decidable/ recursively enumerable languages), coRE, union, intersection, reverse |
| 4 | Other closure properties of \mathbf{R}, \mathbf{RE}, and \mathbf{coRE} | R (decidable/recursive languages), RE (semi-decidable/ recursively enumerable languages), coRE, complement, concatenation, Kleene star, shift |
| 5 | \mathbf{R}, \mathbf{RE}, and \mathbf{coRE} and homomorphisms | R (decidable/recursive languages), RE (semi-decidable/ recursively enumerable languages), coRE, homomorphism, inverse homomorphism |
| 6 | Some languages in \mathbf{RE} | RE (semi-decidable/ recursively enumerable languages) |
| 7 | \mathbf{R}, \mathbf{RE}, \mathbf{coRE}, and symmetric difference | R (decidable/recursive languages), RE (semi-decidable/ recursively enumerable languages), coRE, symmetric difference |
| 8 | Characterizations of \mathbf{R} and \mathbf{RE} | R (decidable/recursive languages), RE (semi-decidable/ recursively enumerable languages), computable functions |
| 9 | Projection of \mathbf{RE} | RE (semi-decidable/ recursively enumerable languages) |
| 10 | On computable functions | computable functions |
Homework 6
Resources useful to solve the exercises in this problem set are the following:
Guille Godoy’s video lectures
Books
- (Sipser 2013, \S 4.2 and \S 5)
- (Serna et al. 2004, \S 4)
- (Hopcroft, Motwani, and Ullman 2007, \S 9)
- (Kozen 1997, Lecture 33)
The following exercises use common notation in computability, in particular, given n\in \mathbb N,
- M_n denotes the Turing machine with Gödel number n.
- \varphi_n denotes the function computed by the Turing machine with Gödel number n.
Given a Turing machine M,
- M(x)\!\uparrow means that M on input x does not terminate.
- M(x)\!\downarrow means that M on input x terminates.
- M(x)=y means that M on input x terminates and give as output y.
With K we denote the set of all natural numbers n such that M_n with input n terminates:
K=\{n\mid M_n(n)\!\downarrow\}\ .
We saw in class that K\in \mathbf{RE}\setminus \mathbf{R}.
Recall that given two languages A, B over the same alphabet \Sigma, we say that A many-one reduces to B (denoted as A\leq_m B) if there exists a total computable function f:\Sigma^*\to\Sigma^* s.t. for every w\in \Sigma^*, w\in A if and only if f(w)\in B.
A useful property of many-one reductions is the following: given A\leq_m B,
- if B\in \mathbf{R}, then A\in \mathbf{R},
- if B\in \mathbf{RE}, then A\in \mathbf{RE}, and
- if B\in \mathbf{coRE}, then A\in \mathbf{coRE}.
The m in \leq_m stands for the fact that f is many-one, that is, not necessarily injective.
| # | Title | Categories |
|---|---|---|
| 1 | Classification I: basic properties of TMs | R (decidable/recursive languages), RE (semi-decidable/ recursively enumerable languages), coRE |
| 2 | Classification II: computable languages | R (decidable/recursive languages), RE (semi-decidable/ recursively enumerable languages), coRE |
| 3 | Classification III: domain of computable functions | R (decidable/recursive languages), RE (semi-decidable/ recursively enumerable languages), coRE |
| 4 | Classification IV: image of computable functions | R (decidable/recursive languages), RE (semi-decidable/ recursively enumerable languages), coRE |
| 5 | Classification V: properties of computable functions | R (decidable/recursive languages), RE (semi-decidable/ recursively enumerable languages), coRE |
| 6 | Classification VI: variations on K | R (decidable/recursive languages), RE (semi-decidable/ recursively enumerable languages) |
| 7 | On the image of decidable sets | R (decidable/recursive languages), RE (semi-decidable/ recursively enumerable languages) |
| 8 | Are they computable? | R (decidable/recursive languages), RE (semi-decidable/ recursively enumerable languages) |
| 9 | Are they (computable) functions? | R (decidable/recursive languages), RE (semi-decidable/ recursively enumerable languages) |
Homework 7
Resources useful to solve the exercises in this problem set are the following:
Sipser’s video lectures
Books
- (Sipser 2013, \S 7)
- (Hopcroft, Motwani, and Ullman 2007, \S 10 and \S 11.1)
| # | Title | Categories |
|---|---|---|
| 1 | Travelling salesperson problem | polynomial time, exponential time |
| 2 | Searching for cliques | polynomial time, exponential time, NP-completeness |
| 3 | Closure properties of \mathsf{P}, \mathsf{NP} and \mathsf{coNP} | P, NP, coNP |
| 4 | Polynomial-time reductions | polynomial-time reductions |
| 5 | Closure under the Kleene star | P, NP, Kleene star |
| 6 | Search vs decision | P, NP, polynomial time |
| 7 | Berman’s theorem | P, NP, NP-completeness, unary language |
| 8 | \mathsf{NP} and \mathtt{HALT} | NP, NP-completeness |
| 9 | \mathtt{Unique SAT} | NP, coNP, DP, Unique SAT |
| 10 | Are they in \mathsf{P}? | NP, P, 3SAT |
References
Footnotes
The use of the Greek word \epsilon (epsilon) seems to be connected to the English word empty. German wikipedia claims the usage of the Greek word \lambda (lambda) is connected to the German leer, which means empty. It is possible that the usage of \lambda to denote the empty string originated in the Finnish school and the influential work of the mathematician Arto Salomaa. Some people in combinatorics use 1 for the empty string with some algebraic justification.↩︎