⟸ pàgina anterior ⟸

Exercici 5 (Tasca 1).

(theory of languages, reverse)

Revessat – propietats bàsiques

Justifiqueu les respostes a les preguntes següents.

1. El revessat de la concatenació (1). Demostreu que per tot parell de mots x,y, (xy)^R=y^Rx^R. Es compleix la propietat anàloga per llenguatges? És a dir, donats dos llenguatges L_1,L_2, es compleix que (L_1L_2)^R=L_2^RL_1^R?
2. El revessat de la concatenació (2). És veritat que, donats dos llenguatges L_1,L_2 tals que (L_1L_2)^R=L_1^R L_2^R, es compleix L_1=L_2 necessàriament?
3. Distribueix el revessat sobre la reunió? És a dir, donats llenguatges L_1,L_2, es compleix que (L_1\cup L_2)^R=L_1^R\cup L_2^R?
4. Distribueix el revessat sobre la intersecció? És a dir, donats llenguatges L_1,L_2, es compleix que (L_1\cap L_2)^R=L_1^R\cap L_2^R?
5. Commuten el complementari i el revessat de llenguatges? És a dir, és cert que \overline{L}^R=\overline{L^R}?
6. Commuten l’estrella de Kleene i el revessat d’un llenguatge? És a dir, és cert que (L^*)^R=(L^R)^*?