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\epsilon =\epsilon 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\ne \epsilon$ e $v\ne \epsilon$.

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: $(\epsilon {)}^R=\epsilon$

Ripetizione o potenza

Si definisce ripetizione o potenza di una stringa la concatenazione di se stessa $m$ volte:

$x^m=\underset{\text{m}}{\underbrace{xxxx...x}}$ con $m\ge 1$. Se $m=0$, allora $x^m=x^0=\epsilon$

Esempi:

• $x=ab\to x^5=ababababab$
• $x=\epsilon \to x^5=\epsilon$
• $x=ab\to x^0=\epsilon$

N.B.: ripetizione e riflessione hanno la precedenza sulla concatenzione! Esempio: $a{b}^2=abb$ e $a{b}^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|\mathrm{\exists }y(y\in L\wedge x=y^R)\}$

Concatenazione

La concatenazione di un linguaggio è definita come il linguaggio contenente la concatenazione delle stringhe dei linguaggi concatenati:

$L^{\prime }{L}^{″}=\{xy|x\in L^{\prime }\wedge y\in L^{″}\}$

N.B.

• $L\cdot \varnothing =\varnothing \cdot L=\varnothing$
• $L\cdot \{\epsilon \}=\{\epsilon \}\cdot L=L$

Ripetizione o potenza

La ripetizione o potenza di un linguaggio viene definita ricorsivamente:

$L^m=L^{m-1}L$ per $m\ge 1$

$L^0=\{\epsilon \}$

N.B. ${\varnothing }^0=\{\epsilon \}$

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,\epsilon \}\to L^2=\{a^2,b^2,c^2,ab,ac,ba,ca,bc,cb,a,b,c,\epsilon \}$

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 $\mathrm{\Sigma }$ come l'insieme di tutte le stringhe di qualsiasi lunghezza sull'alfabeto:

$L_{\text{universale}}={\mathrm{\Sigma }}^0\cup {\mathrm{\Sigma }}^1\cup {\mathrm{\Sigma }}^2\cup ...$

Definiamo complemento di un linguaggio $\mathrm{\neg }L$ su un alfabeto $\mathrm{\Sigma }$:

$\mathrm{\neg }L=L_{\text{universale}}\setminus L$

N.B.:

• $L_{\text{universale}}=\mathrm{\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,...,\mathrm{\infty }}{L}^h=L^0\cup L^1\cup ...=\{\epsilon \}\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^{*}=\{\epsilon ,ab,ba,fg,abab,abba,abfg,baab,baba,bafg,...$

$L^{*}$ è evidentemente sempre infinito, qualsiasi sia il linguaggio $L\ne \{\epsilon \}\ne \varnothing$. Può capitare che $L=L^{*}$, ad esempio: $L=\{a^n,n\ge 0\}=L^{*}$.

N.B.: $L_{\text{universale}}={\mathrm{\Sigma }}^{*}$

Spesso si utilizza la sintassi $L\subseteq {\mathrm{\Sigma }}^{*}$ per dire che il linguaggio $L$ è un linguaggio sull'alfabeto $\mathrm{\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 }^{*}=\{\epsilon \}$
• ${\epsilon }^{*}=\{\epsilon \}$

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,...,\mathrm{\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|(\mathrm{\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\ge 0\}$

$L_1/L_2=\{a^{2}b,a^{4}b,a^{4}b,...\}$