Exercicis per a l’avaluació continuada

Cases, Rafel, i Lluís Màrquez. 2003. Llenguatges, gramàtiques i autòmats : curs bàsic. 2a ed. Edicions UPC.

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

Kozen, Dexter. 1997. Automata and computability. Undergraduate texts a computer science. Springer.

Sipser, Michael. 2013. Introduction to the theory of computation. 3rd edition. Cengage Learning.

Aquesta secció conté una llista d’exercicis sobre els temes tractats al curs. Els exercicis estan agrupats en Tasques (T).

Al racó, aproximadament cada dues setmanes, se t’assignarà un exercici d’una tasca (o una part d’un exercici). Consulta el racó per veure quin exercici t’ha estat assignat i prepara’t per presentar la teva solució a la pissarra.

Es recomana discutir les solucions amb altres estudiants i treballar en grup (especialment amb estudiants als quals se’ls hagi assignat parts del mateix exercici). Ara bé, a classe, les presentacions a la pissarra són individuals.

Sobre la notació

En els exercicis següents fem servir notació matemàtica estàndard i alguna de lleugerament no estàndard:

• \lambda denota el mot buit. En la majoria de llibres, això es representa amb \epsilon: aquest és el cas, per exemple, de (Sipser 2013), (Hopcroft, Motwani, i Ullman 2007) i (Kozen 1997).

• Donat n\in \mathbb N, fem servir n\mathbb N o \dot n per representar el conjunt dels naturals múltiples de n. Escriure m\in n\mathbb N +k és el mateix que afirmar que m\equiv k \pmod{n}. Per exemple, és cert que 6\in 3\mathbb N i 16\in 5\mathbb N +1, mentre que 13\notin 7\mathbb N.

• Per a un mot binari w, \mathtt{value}_2(w) representa el valor binari del mot w. Per convenció, \mathtt{value}_2(\lambda)=0. Observem que \mathtt{value}_2(w0)=2\cdot\mathtt{value}_2(w) i \mathtt{value}_2(w1)=2\cdot\mathtt{value}_2(w)+1. Cal notar també que un nombre arbitrari de zeros inicials en un mot dona lloc al mateix nombre: \mathtt{value}_2(w)=\mathtt{value}_2(0w)=\mathtt{value}_2(00w)=\mathtt{value}_2(000w)=\cdots. En particular, per a cada nombre natural n hi ha infinits mots binaris w tals que \mathtt{value}_2(w)=k.