⟸ pàgina anterior ⟸
Exercici 4 (Tasca 1).
(Kleene star, theory of languages)

Caracteritzacions

Justifiqueu les vostres respostes a les preguntes següents. Els llenguatges estan definits sobre un alfabet fixat qualsevol.

  1. Quan és un llenguatge igual al seu tancament positiu? Es compleix L=L^+ si i només si L^2 \subseteq L?
  2. Quan és un llenguatge igual a la seva estrella de Kleene? És L^2\subseteq L una condició necessària per la igualtat L= L^*? És \lambda \in L una condició necessària per L= L^*? Quina combinació lògica (\land, \lor, …) de les afirmacions L^2\subseteq L i \lambda\in L constitueix una condició necessària i suficient per la igualtat L= L^*?
  3. Quan està un llenguatge inclòs en el seu quadrat? És \lambda\in L una condició suficient per la inclusió L\subseteq L^2? És L = \emptyset una condició suficient per L\subseteq L^2? Quina combinació lògica (\land, \lor, …) de les afirmacions L = \emptyset i \lambda\in L constitueix una condició suficient i necessària per la inclusió L\subseteq L^2?
  4. Quan és un llenguatge igual al seu quadrat? És L=L^* una condició suficient per la igualtat L= L^2? És L = \emptyset una condició suficient per L= L^2? Quina combinació lògica (\land, \lor, …) de les afirmacions L = L^* i L=\emptyset constitueix una condició suficient i necessària per la igualtat L = L^2?

Recordeu que si P i Q són dues proposicions tals que P implica Q, llavors es diu que P és una condició suficient per a Q, mentre que Q és una condició necessària per a P. També es diu que P és una caracterització de Q quan P és una condició tant suficient com necessària per a Q.