Operazioni sui Linguaggi

Operazioni

Fissiamo $\Sigma =\{0,1\}$. Per $n\in \mathbb{N},[u]=\{1,2,...,n\}$. Siccome i linguaggi regolari sono un insieme di stringhe posso considerare su di essi operazioni.

• Unione: $L_1\cup L_2=\{x\in {\Sigma }^{\ast }|x\in L_{1}oppurex\in L_2\}$
• Intersezione: $L_1\cap L_2=\{x\in {\Sigma }^{\ast }|x\in L_{1}ex\in L_2\}$
• Complemento: $\overline{L_1}=\{x\in {\Sigma }^{\ast }|x\notin L_1\}$
• Concatenazione: Se abbiamo (per le stringhe)

$$\begin{array}{c}x=a_1,...,a_n,y=b_1,...,b_{m}n,m>0\\ xy=a_1,...,a_n,b_1,...,b_m\in {\Sigma }^{\ast }\\ ϵx=xϵ=x\\ \{\begin{array}{l}xϵ=x\\ x(ya)=(xy)a\\ x,y\in {\Sigma }^{\ast },a\in \Sigma \end{array}\end{array}$$

Posso concatenare anche linguaggi: $L_1\circ L_2=\{xy:x\in L_{1}ey\in L_2$ .

Sono tutte le possibili combinazione dei due insiemi prendendo uno dei due come "primo"

Esempio

$\Sigma =\{a,b\},L_1=\{a,ab,ba\},L_2=\{ab,b\}{L}_1\circ L_2=\{aab,ab,abab,abb,baab,bab\}$

N.B. $L_1\circ L_2\ne L_1\cup L_2$

• Potenza: Per le stringhe: $$\begin{array}{c}{x}^n=x...xnvoltex\in {\Sigma }^{\ast }\\ x^0=ϵ\\ x^{u+1}=x^{u}x\end{array}$$

Lo stesso vale per i linguaggi

$$\begin{array}{c}{L}^0=\{ϵ\}\\ L^{u+1}=L^u\circ L\end{array}$$

Sono tutte le possibili combinazioni (con n passi dove n e l'esponente) combinando se stesso

Esempio

$L=\{a,ab,ba\}{L}^2=\{aa,aab,aba,abab,abba,baa,baab.baba\}$

• La Star (*): $L^{\ast }={\bigcup }_{u\ge 0}{L}^n=\{ϵ\}\cup L^1\cup L^2\cup ...\cup L^n$

Esempio

$L=\{a,b\}{L}^{\ast }=\{ϵ,a,b,aa,ab,bb,ba,aaa,...\}$

Proprieta

Vogliamo studiare la proprieta di chiusura dei linguaggi regolari. Ovver: se $L_1,L_2\in REG$, posso dire che $L_1\cup L_2\in REG$? $L_1\cap L_2$? $\overline{L_1}$? $L_1^{\ast }$?

Teorema: REG chiusa per unione

Intuizione: $L_1,L_2\in REG\to \exists M_1,M_2\in DFAt.c.L(M_1)=L_1,L(M_2)=L_2$ Devo definire M t.c. $L(M)=L_1\cup L_2$.

Problema: Dato x candidato non posso andare prima a vedere se $M_1(x)$ accetta (l’automa avrebbe gia esaurito la stringa e non potrebbe verificarla per $M_2$).

Idea: Devo farla in parallelo su $M_1,M_2$ e accettare $\iff$ uno dei due automi accetta.

…