# Operazioni sui linguaggi formali
## Operazioni sulle stringhe
### Concatenazione

La concatenzione tra due stringhe, detto anche prodotto tra due stringhe, è definito come:
    siano $x=a_{1}a_{2}...a_{h}$ e $y=b_{1}b_{2}...b_{k}$ due stringhe, allora la loro concatenzione è $xy=a_{1}a_{2}...a_{h}b_{1}b_{2}...b_{k}$.
La concatenzione è anche indicata con $xy=x\cdot y$. Gode della proprietà associativa $x(yz)=(xy)z$ e dell'additività della lunghezza $|xy|=|x|+|y|$.
Ha come elemento neutro la stringa vuota: $x\varepsilon =\varepsilon x=x$.

### Sottostringa

Diciamo che $y$ è sottostringa di $x$ se e solo se:
    $x=uyv$ per qualche stringa $u$ (detta prefisso) e $v$ (detta suffisso).
$y$ è sottostringa propria se e solo se $u\neq \varepsilon$ e $v\neq \varepsilon$.

### Riflessione

L'operazione di riflessione è definita come:
    sia $x=a_{1}a_{2}...a_{k-1}a_{k}$ allora la sua riflessione è $x^{R}=a_{k}a_{k-1}...a_{2}a_{1}$.
Gode delle seguenti proprietà:
* riflessiva: $(x^{R})^{R}=x$
* distributiva: $(xy)^{R}=y^{R}\cdot x^{R}$
* valore nullo: $(\varepsilon )^{R}=\varepsilon$

### Ripetizione o potenza

Si definisce ripetizione o potenza di una stringa la concatenazione di se stessa $m$ volte:
    $x^{m}=\underbrace {xxxx...x} _{\text{m}}$ con $m\geq 1$. Se $m=0$, allora $x^{m}=x^{0}=\varepsilon$
Esempi:
* $x=ab\to x^{5}=ababababab$
* $x=\varepsilon \to x^{5}=\varepsilon$
* $x=ab\to x^{0}=\varepsilon$
N.B.: ripetizione e riflessione hanno la precedenza sulla concatenzione! Esempio: $ab^{2}=abb$ e $ab^{R}=ab$.

## Operazioni sui linguaggi

Alcune operazioni sui linguaggi sono l'estensione di quelle sulle stringhe.

### Riflessione

La riflessione di un linguaggio è l'insieme di tutte le stringhe riflesse del linguaggio:
    sia $L$ un linguaggio, allora $L^{R}=\{x|\exists y(y\in L\land x=y^{R})\}$

### Concatenazione

La concatenazione di un linguaggio è definita come il linguaggio contenente la concatenazione delle stringhe dei linguaggi concatenati:
    $L'L''=\{\ xy\ |\ x\in L'\land y\in L''\ \}$
N.B.
* $L\cdot \varnothing =\varnothing \cdot L=\varnothing$
* $L\cdot \{\varepsilon \}=\{\varepsilon \}\cdot L=L$

### Ripetizione o potenza

La ripetizione o potenza di un linguaggio viene definita ricorsivamente:
    $L^{m}=L^{m-1}L$ per $m\geq 1$
    $L^{0}=\{\varepsilon \}$
N.B. $\varnothing ^{0}=\{\varepsilon \}$
Esempio: $L=\{a,b,c\}\to L^{2}=\{a^{2},b^{2},c^{2},ab,ac,ba,ca,bc,cb\}\$
Come visto la potenza produce un set di stringhe di dimensione fissa e finita $m$. Utilizzando la stringa vuota è possibile ottenere il set di stringhe con lunghezza minore di m.
Esempio: $L=\{a,b,c,\varepsilon \}\to L^{2}=\{a^{2},b^{2},c^{2},ab,ac,ba,ca,bc,cb,a,b,c,\varepsilon \}\$

### Operazioni insiemistiche

I linguaggi godono delle classiche operazioni insiemistiche:
* $\cup$: unione (insieme composto da tutte le stringhe che compongono il primo linguaggio o il secondo linguaggio.)
* $\cap$: intersezione (insieme composto da tutte le stringhe che compongono il primo linguaggio e il secondo linguaggio.)
* $\setminus$: differenza (insieme composto da tutte le stringhe che compongono il primo linguaggio ma non il secondo linguaggio.)
* $\subseteq$: inclusione
* $\subset$: inclusione stretta
* $=$: uguaglianza

#### Definizioni

Definiamo linguaggio universale $L_{\text{universale}}$ di un alfabeto $\Sigma$ come l'insieme di tutte le stringhe di qualsiasi lunghezza sull'alfabeto:
    $L_{\text{universale}}=\Sigma ^{0}\cup \Sigma ^{1}\cup \Sigma ^{2}\cup ...$
Definiamo complemento di un linguaggio $\neg L$ su un alfabeto $\Sigma$:
    $\neg L=L_{\text{universale}}\setminus L$
N.B.:
* $L_{\text{universale}}=\neg \varnothing$.
* Il complemento di un linguaggio finito è sempre infinito;
* Il complemento di un linguaggio infinito non è sempre finito.

### Chiusura di Kleene

La chiusura di Kleene o operatore stella è la chisura riflessiva e transitiva dell'operazione di concatenazione.
    $L^{*}=\bigcup _{h=0,...,\infty }L^{h}=L^{0}\cup L^{1}\cup ...=\{\varepsilon \}\cup L^{1}\cup ...$
Informalmente, questo insieme di stringhe è quello che è possibile generare concatenando due stringhe di L, anche con ripetizioni.
Ad esempio:
    $L=\{ab,ba,fg\}\ \to \ L^{*}=\{\varepsilon ,ab,ba,fg,abab,abba,abfg,baab,baba,bafg,...$
$L^{*}$ è evidentemente sempre infinito, qualsiasi sia il linguaggio $L\neq \{\varepsilon \}\neq \varnothing$. Può capitare che $L=L^{*}$, ad esempio: $L=\{a^{n},n\geq 0\}=L^{*}$.
N.B.: $L_{\text{universale}}=\Sigma ^{*}$
Spesso si utilizza la sintassi $L\subseteq \Sigma ^{*}$ per dire che il linguaggio $L$ è un linguaggio sull'alfabeto $\Sigma$.

#### Proprietà

La chiusura di Kleene gode delle seguenti proprietà:
* monotonicità: $L\subseteq L^{*}$
* chiusura alla concatenazione: ${\text{if }}x\in L^{*}{\text{ and }}y\in L^{*}{\text{ then }}xy\in L^{*}$
* idempotenza: $(L^{*})^{*}=L^{*}$
* commutatività con riflessione: $(L^{*})^{R}=(L^{R})^{*}$
* $\varnothing ^{*}=\{\varepsilon \}$
* $\varepsilon ^{*}=\{\varepsilon \}$

### Operatore Cross

L'operatore cross è la chisura transitiva ma non riflessiva dell'operazione di concatenazione. Sostanzialmente rispetto al precedente l'unione non include la prima potenza $L^{0}$
    $L^{+}=\bigcup _{h=1,...,\infty }L^{h}=L^{1}\cup L^{2}\cup ...$

### Operatore quoziente

L'operatore quoziente, identificato dalla slash $L_{1}/L_{2}$ (non backslash!). Definito come: $L_{1}/L_{2}=\{\ u\ |(\ \exists w\in L_{2}|uw\in L_{1}L_{2})\ \}$.
Esempio:
    $L_{1}=\{\ a^{2n}b^{2n}|n>0\ \}$
    $L_{2}=\{\ b^{2n+1}|n\geq 0\ \}$
    $L_{1}/L_{2}=\{\ a^{2}b,a^{4}b,a^{4}b,...\ \}$