Exercises for the continuous assessment

Cases, Rafel, and Lluís Màrquez. 2003. Llenguatges, Gramàtiques i Autòmats : Curs Bàsic. 2a ed. Edicions UPC.

Hopcroft, John E., Rajeev Motwani, and Jeffrey D. Ullman. 2007. Introduction to Automata Theory, Languages, and Computation. 3rd edition. Pearson Addison Wesley.

Kozen, Dexter. 1997. Automata and Computability. Undergraduate Texts in Computer Science. Springer.

Sipser, Michael. 2013. Introduction to the Theory of Computation. 3rd edition. Cengage Learning.

This section contains a list of exercises on the topics covered in the course. The exercises are grouped into Problem Sets (PS).

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 following exercises 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).

• 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.