[Teoria] verificare se un linguaggio e' regolare

[cicchi27]

Salve ho questo esercizio:

"Data una parola v sull’alfabeto {a, b}, denotiamo con v2 la parola ottenuta da
v raddoppiando ogni lettera. Dato un linguaggio L denotiamo con
L2 = {v2| v ∈ L}.
Se L è un linguaggio regolare L2 è regolare? Il linguaggio LL2 è anch’esso
regolare? Motivare la risposta."

Ho dei dubbi per rispondere alla prima domanda: è possibile usare il pumping lemma per L2 pur sapendo che L è un generico linguaggio regolare? Qualche spunto? Per la seconda domanda, invece, la risposta dipenderà se dalla prima in quanto c'è la chiusura rispetto all concatenazione. Grazie in anticipo.

[apatriarca]

Credo che sia più facile usare la definizione di linguaggio regolare in questo caso. In particolare, esiste un'espressione regolare che definisce il nostro linguaggio \(L\). L'idea è quella di mostrare un algoritmo per costruire l'espressione regolare di \(L2\). L'algoritmo è il seguente:
\[
\begin{align*}
L2(a) &= a\,a \\
L2(b) &= b\,b \\
L2(E^*) &= L2(E)^* \\
L2(E \cup F) &= L2(E) \cup L2(F) \\
L2(E\,F) &= L2(E)\,L2(F)
\end{align*}
\]
In pratica sostituisci ogni \(a\) o \(b\) con la lettera raddoppiata.

Se quindi hai ad esempio qualcosa come
\[ L = a \, \Big( \big( (a \, b)^* \, b \bigr) \cup a \, (a \, b)^*\Bigr) \]
Allora \(L2\) avrà espressione regolare
\[ L2 = a \, a \, \Big( \big( (a \, a \, b \, b)^* \, b \, b \bigr) \cup a \, a \, (a \, a \, b \, b)^* \Bigr) \]