La concatenzione tra due stringhe, detto anche prodotto tra due stringhe, è definito come:
- siano
e
due stringhe, allora la loro concatenzione è
.
La concatenzione è anche indicata con
. Gode della proprietà associativa
e dell'additività della lunghezza
.
Ha come elemento neutro la stringa vuota:
.
Diciamo che
è sottostringa di
se e solo se:
per qualche stringa
(detta prefisso) e
(detta suffisso).
è sottostringa propria se e solo se
e
.
L'operazione di riflessione è definita come:
- sia
allora la sua riflessione è
.
Gode delle seguenti proprietà:
- riflessiva:
![{\displaystyle (x^{R})^{R}=x}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a506581c63ca09a57a99f79cadf29c676f42ffa0)
- distributiva:
![{\displaystyle (xy)^{R}=x^{R}\cdot y^{R}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5ddbf6d278397372d16637031ff4b86d808b7717)
- valore nullo:
![{\displaystyle (\varepsilon )^{R}=\varepsilon }](https://wikimedia.org/api/rest_v1/media/math/render/svg/7e07c3444840cfbe80205799beccbcbf40497c95)
Si definisce ripetizione o potenza di una stringa la concatenazione di se stessa
volte:
con
. Se
, allora ![{\displaystyle x^{m}=x^{0}=\varepsilon }](https://wikimedia.org/api/rest_v1/media/math/render/svg/4141197ba067d6619f2566ba627da2c6893c3796)
Esempi:
![{\displaystyle x=ab\to x^{5}=ababababab}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7f8ced2b841fe236b74819e6b0c1c480334bfcba)
![{\displaystyle x=\varepsilon \to x^{5}=\varepsilon }](https://wikimedia.org/api/rest_v1/media/math/render/svg/439895a407d0f89cc9e6b31354da9b5637def86d)
![{\displaystyle x=ab\to x^{0}=\varepsilon }](https://wikimedia.org/api/rest_v1/media/math/render/svg/1b257b7dba58130223e01bbe6a543bb5cebeacd6)
N.B.: ripetizione e riflessione hanno la precedenza sulla concatenzione! Esempio:
e
.
Alcune operazioni sui linguaggi sono l'estensione di quelle sulle stringhe.
La riflessione di un linguaggio è l'insieme di tutte le stringhe riflesse del linguaggio:
- sia
un linguaggio, allora ![{\displaystyle L^{R}=\{x|\exists y(y\in L\land x=y^{R})\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4a85cdb4aaca48d54fac2deb59bf6e7dbb8dced0)
La concatenazione di un linguaggio è definita come il linguaggio contenente la concatenazione delle stringhe dei linguaggi concatenati:
![{\displaystyle L'L''=\{\ xy\ |\ x\in L'\land y\in L''\ \}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6721e8e3c15f8d9bb5506f14d34a51524a2e7754)
N.B.
![{\displaystyle L\cdot \varnothing =\varnothing \cdot L=\varnothing }](https://wikimedia.org/api/rest_v1/media/math/render/svg/fb873a245aa32abd0223be26d1a4e62ca4a670dd)
![{\displaystyle L\cdot \{\varepsilon \}=\{\varepsilon \}\cdot L=L}](https://wikimedia.org/api/rest_v1/media/math/render/svg/41e9a174cd5426ca426a9e66a2c6876603088299)
La ripetizione o potenza di un linguaggio viene definita ricorsivamente:
per ![{\displaystyle m\geq 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1e0f3243e9d7f06bee548558bf20aaa9b5263d3f)
![{\displaystyle L^{0}=\{\varepsilon \}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dc08450ee740bb33eba225755a714a71dd8684d0)
N.B.
Esempio:
Come visto la potenza produce un set di stringhe di dimensione fissa e finita
. Utilizzando la stringa vuota è possibile ottenere il set di stringhe con lunghezza minore di m.
Esempio:
I linguaggi godono delle classiche operazioni insiemistiche:
: unione (insieme composto da tutte le stringhe che compongono il primo linguaggio o il secondo linguaggio.)
: intersezione (insieme composto da tutte le stringhe che compongono il primo linguaggio e il secondo linguaggio.)
: differenza (insieme composto da tutte le stringhe che compongono il primo linguaggio ma non il secondo linguaggio.)
: inclusione
: inclusione stretta
: uguaglianza
Definiamo linguaggio universale
di un alfabeto
come l'insieme di tutte le stringhe di qualsiasi lunghezza sull'alfabeto:
![{\displaystyle L_{\text{universale}}=\Sigma ^{0}\cup \Sigma ^{1}\cup \Sigma ^{2}\cup ...}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8cddfbeae4be97b6073d7f17577b499735dd3794)
Definiamo complemento di un linguaggio
su un alfabeto
:
![{\displaystyle \neg L=L_{\text{universale}}\setminus L}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5cbc10cb9401d3d73e3a627c2542d7df02d9b69)
N.B.:
.
- Il complemento di un linguaggio finito è sempre infinito;
- Il complemento di un linguaggio infinito non è sempre finito.
La chiusura di Kleene o operatore stella è la chisura riflessiva e transitiva dell'operazione di concatenazione.
![{\displaystyle L^{*}=\bigcup _{h=0,...,\infty }L^{h}=L^{0}\cup L^{1}\cup ...=\{\varepsilon \}\cup L^{1}\cup ...}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0daf32deccea7a244d71da7c4930d566c25b0d14)
Informalmente, questo insieme di stringhe è quello che è possibile generare concatenando due stringhe di L, anche con ripetizioni.
Ad esempio:
![{\displaystyle L=\{ab,ba,fg\}\ \to \ L^{*}=\{\varepsilon ,ab,ba,fg,abab,abba,abfg,baab,baba,bafg,...}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ee23465a046fcf4863aba18c1d5a2b97e628e9f1)
è evidentemente sempre infinito, qualsiasi sia il linguaggio
. Può capitare che
, ad esempio:
.
N.B.:
Spesso si utilizza la sintassi
per dire che il linguaggio
è un linguaggio sull'alfabeto
.
La chiusura di Kleene gode delle seguenti proprietà:
- monotonicità:
![{\displaystyle L\subseteq L^{*}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b39cdb95421085badf986767ae33e52b13048426)
- chiusura alla concatenazione:
![{\displaystyle {\text{if }}x\in L^{*}{\text{ and }}y\in L^{*}{\text{ then }}xy\in L^{*}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9e8ef8793da9001113f0e10d06e8bff388b907e1)
- idempotenza:
![{\displaystyle (L^{*})^{*}=L^{*}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8f41dd68b3435e328622ba89f5f91c91efd2f67a)
- commutatività con riflessione:
![{\displaystyle (L^{*})^{R}=(L^{R})^{*}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e420c5cc7f4c17eeb764478d8243dd1277e88d01)
![{\displaystyle \varnothing ^{*}=\{\varepsilon \}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6d27c42f8da5fb9d13e2618deb1e76529bc1e291)
![{\displaystyle \varepsilon ^{*}=\{\varepsilon \}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/494de66ec3f54f553439fc1e2d80f80c2501811c)
L'operatore cross è la chisura transitiva ma non riflessiva dell'operazione di concatenazione. Sostanzialmente rispetto al precedente l'unione non include la prima potenza
![{\displaystyle L^{+}=\bigcup _{h=1,...,\infty }L^{h}=L^{1}\cup L^{2}\cup ...}](https://wikimedia.org/api/rest_v1/media/math/render/svg/96d546025de2ed711785add798518346ca2df276)
L'operatore quoziente, identificato dalla slash
(non backslash!). Definito come:
.
Esempio:
![{\displaystyle L_{1}=\{\ a^{2n}b^{2n}|n>0\ \}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4d50081fbcc62cc12a88481b7f780b9720826a4d)
![{\displaystyle L_{2}=\{\ b^{2n+1}|n\geq 0\ \}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d6936f18845a71fbff4c10a218098f4a3a190e39)
![{\displaystyle L_{1}/L_{2}=\{\ a^{2}b,a^{4}b,a^{4}b,...\ \}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bf26155f4f305aad19fcdde23ce43e82d11b447f)