Unione su linguaggi

[noipo]

Ciao a tutti.
Ho i seguenti linguaggi:
$L_1 = {a^n b^n | n >= 0}$
$L_2 = {a^n b^m c^p | n = m +p & n >= 0}$
$L_3 = {a^n c b^n | n >= 0}$
$L_4 = {(ab)^n (cd)^n | n >= 0}$
$L_5 = {a^n b^m c^m d^n | n,m >= 0}$
$L_6 = {b^m a^(2k) b^m a^n | k,m >= 0 & n > 0}$
$L_7 = {a^n b^m c^p d^q | n,m,p,q >= 0 & n+m=p+q}$

Ora dovrei trovare i linguaggi generati dalle varie combinazioni di unione. Cioè:
$L_1 uu L_2$, $L_1 uu L_3$, $L_1 uu L_4$, $L_1 uu L_5$, $L_1 uu L_6$, $L_1 uu L_7$, $L_2 uu L_3$, $L_2 uu L_4$, $L_2 uu L_5$, $L_2 uu L_6$, $L_2 uu L_7$, $L_3 uu L_4$, $L_3 uu L_5$, $L_3 uu L_6$ , $L_3 uu L_7$, $L_4 uu L_5$, $L_5 uu L_6$, $L_4 uu L_7$, $L_5 uu L_6$, $L_5 uu L_7$ e $L_6 uu L_7$.

So che , $L_1 uu L_2 = L_2 = L_2 uu L_1$. Questo è un esempio semplice, i successivi non riesco a farli. C'è una procedura "meccanica" per svolgere questo tipo di esercizio?

Per esempio $L_1 uu L_3 = L_3$, è giusto? Mentre invece $L_1 uu L_4 = ?$, non è ne uguale a $L_1$ nè a $L_4$ quindi a cosa corrisponde?

Grazie

[onlyReferee]

Ciao vfldj
Allora, teniamo innanzitutto presente la definizione dell'operazione di unione tra linguaggi. Detti $L_1$ e $L_2$ linguaggi la loro unione è definita da:
\[
L_1 \cup L_2 = \{u \text{ }|\text{ } u \in L_1 \lor u \in L_2\}
\]
Ora, te giustamente stai cercando di vedere se eventualmente tra i linguaggi presenti ce n'è già uno che rappresenti l'unione di quelli presi correntemente in considerazione. Vediamo:

[*:6fj3356d]$L_1 \cup L_2 = L_2$: corretto. Ponendo infatti per $L_2 \text{ } p = 0$ ne risulta $m = n$ e sotto questi condizioni $L_ 1 = L_2$;[/*:m:6fj3356d]
[*:6fj3356d]$L_1 \cup L_3 = L_3$: non è corretto. Con l'espressione regolare che denota $L_3$ non riuscirai mai a generare le stringhe di $L_1$ e si possono fornire numerosissimi controesempi poiché $c$ è fisso e non si riesce in alcun modo a toglierlo (prendi ad esempio la stringa $aabb$ che è possibile generare solo con l'espressione regolare di $L_1$ ma non con quella di $L_3$);[/*:m:6fj3356d]
[*:6fj3356d]$L_1 \cup L_4 = \{(a^nb^n) + (ab)^n(cd)^n \text{ }|\text{ } n \geq 0\}$. Questa unione difatti la possiamo scrivere soltanto così (almeno non vedo altre combinazioni/unioni a partire dagli altri linguaggi definiti che permettano di riscriverla diversamente).[/*:m:6fj3356d][/list:u:6fj3356d]
Sostanzialmente l'unica regola abbastanza "meccanica" che si può usare è proprio quella che ho evidenziato all'ultimo punto (ossia combini le espressioni regolari dei due linguaggi mediante l'operatore $+$). Solo in seguito conviene provare a vedere se è possibile riscrivere tale espressione mediante i linguaggi già esistenti semplificando pertanto la notazione.
Spero di esserti stato d'aiuto intanto, caso mai chiedi pure .

[noipo]

Intanto grazie per la risposta.
Però intendevo $L_1 uu L_3 = L_3$ e non $L_1 uu L_2 = L_3$

$ L_1 \cup L_4 = \{(a^nb^n) + (ab)^n(cd)^n \text{ }|\text{ } n \geq 0\} $

Quando hai scritto: $ L_1 \cup L_4 = \{(a^nb^n) + (ab)^n(cd)^n |n \geq 0\} $, con $+$ intendi il simbolo di concatenazione?

Quindi i "passaggi" da fare sono:
1) Scrivo i due linguaggi da unire nella forma $L_i + L_j$
2) Vedo se riesco a semplificarli

Ma come devo comportarmi al passo 1) per le specifiche degli intervalli delle variabili? Per capirci intendo le notazioni tipo $n>=0$, $0
Provo a fare un esempio per vedere se ho capito il tuo ragionamento:

$L_5 uu L_6 = {a^n b^m c^m d^n + b^y a^(2k) b^y a^x | n,m,y,k \geq 0 & x > 0}$

Ho cambiato i nomi delle variabili di $L_6$ per non confonderle con quelle di $L_5$.
Bene ora dovrei cercare di semplificare il linguaggio.. Mmm e come? A me non sembra semplificabile, mi sbaglio?

[onlyReferee]

"vfldj":Intanto grazie per la risposta.
Però intendevo $L_1 uu L_3 = L_3$ e non $L_1 uu L_2 = L_3$
[...]

Sì, scusa, errore di battitura mio (ho modificato il post), intendevo esattamente come hai chiesto te in realtà.

"vfldj":
[...]
$ L_1 \cup L_4 = \{(a^nb^n) + (ab)^n(cd)^n \text{ }|\text{ } n \geq 0\} $

Quando hai scritto: $ L_1 \cup L_4 = \{(a^nb^n) + (ab)^n(cd)^n |n \geq 0\} $, con $+$ intendi il simbolo di concatenazione?
[...]

No, il simbolo di concatenazione (che talvolta è omesso) è $\cdot$. L'operatore $+$ permette invece di scegliere tra le due possibilità (in questo caso tra le due espressioni regolari dei linguaggi).

"vfldj":
[...]
Quindi i "passaggi" da fare sono:
1) Scrivo i due linguaggi da unire nella forma $L_i + L_j$
2) Vedo se riesco a semplificarli

Ma come devo comportarmi al passo 1) per le specifiche degli intervalli delle variabili? Per capirci intendo le notazioni tipo $n>=0$, $0
Provo a fare un esempio per vedere se ho capito il tuo ragionamento:

$L_5 uu L_6 = {a^n b^m c^m d^n + b^y a^(2k) b^y a^x | n,m,y,k \geq 0 & x > 0}$

Ho cambiato i nomi delle variabili di $L_6$ per non confonderle con quelle di $L_5$.
Bene ora dovrei cercare di semplificare il linguaggio.. Mmm e come? A me non sembra semplificabile, mi sbaglio?

Giusto, se trovi due variabili che si chiamano con lo stesso nome allora semplicemente usi un altro nome per una delle due. Non è detto sia sempre necessario ma...qualora si debba evitare confusione meglio farlo.
Riguardo al tuo esempio. Ora ho visto che il $2k$ è l'indice di $a^{2k}$ (nel tuo post originale penso ci fosse una semplice svista dovuta ad errore di digitazione) e pertanto questo denota un numero pari di $a$.
In questo caso non puoi fare proprio null'altro poiché, come puoi notare, le stringhe di un linguaggio non sono contenute in quelle dell'altro.

[noipo]

Si ho sbagliato a scrivere nel primo post. Ora l'ho modificato.
Perfetto, spero di aver capito e comunque continuo con gli esercizi.
Grazie mille