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}=x^{R}\cdot y^{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,...\ \}$