Wikiversità
itwikiversity
https://it.wikiversity.org/wiki/Pagina_principale
MediaWiki 1.39.0-wmf.23
first-letter
Media
Speciale
Discussione
Utente
Discussioni utente
Wikiversità
Discussioni Wikiversità
File
Discussioni file
MediaWiki
Discussioni MediaWiki
Template
Discussioni template
Aiuto
Discussioni aiuto
Categoria
Discussioni categoria
Area
Discussioni area
Corso
Discussioni corso
Materia
Discussioni materia
Dipartimento
Discussioni dipartimento
Education Program
Education Program talk
TimedText
TimedText talk
Modulo
Discussioni modulo
Accessorio
Discussioni accessorio
Definizione accessorio
Discussioni definizione accessorio
Operazioni sui linguaggi formali
0
15881
259741
232805
2022-08-08T10:24:44Z
151.34.228.245
/* Proprietà */
wikitext
text/x-wiki
{{risorsa|tipo=lezione|materia1=Linguaggi formali e automi|avanzamento=100%}}
== Operazioni sulle stringhe ==
=== Concatenazione ===
La concatenzione tra due stringhe, detto anche prodotto tra due stringhe, è definito come:
: siano <math>x=a_1a_2...a_h</math> e <math>y=b_1b_2...b_k</math> due stringhe, allora la loro concatenzione è <math>xy=a_1a_2...a_hb_1b_2...b_k</math>.
La concatenzione è anche indicata con <math>xy=x\cdot y</math>. Gode della proprietà associativa <math>x(yz)=(xy)z</math> e dell'additività della lunghezza <math>|xy| = |x| + |y|</math>.
Ha come [[w:elemento neutro|elemento neutro]] la stringa vuota: <math>x\varepsilon=\varepsilon x = x</math>.
=== Sottostringa ===
Diciamo che <math>y</math> è '''sottostringa''' di <math>x</math> se e solo se:
: <math>x=uyv</math> per qualche stringa <math>u</math> (detta prefisso) e <math>v</math> (detta suffisso).
<math>y</math> è sottostringa '''propria''' se e solo se <math>u \ne \varepsilon</math> e <math>v \ne \varepsilon</math>.
=== Riflessione ===
L'operazione di riflessione è definita come:
: sia <math>x=a_1a_2...a_{k-1}a_k</math> allora la sua riflessione è <math>x^R = a_ka_{k-1}...a_2a_1</math>.
Gode delle seguenti proprietà:
* riflessiva: <math>(x^R)^R=x</math>
* distributiva: <math>(xy)^R=x^R\cdot y^R</math>
* valore nullo: <math>(\varepsilon)^R=\varepsilon</math>
=== Ripetizione o potenza ===
Si definisce '''ripetizione''' o '''potenza''' di una stringa la concatenazione di se stessa <math>m</math> volte:
: <math>x^m=\underbrace{xxxx...x}_\text{m}</math> con <math>m \ge 1</math>. Se <math>m=0</math>, allora <math>x^m=x^0=\varepsilon</math>
Esempi:
* <math>x=ab\to x^5=ababababab</math>
* <math>x=\varepsilon\to x^5=\varepsilon</math>
* <math>x=ab\to x^0=\varepsilon</math>
'''N.B.''': ripetizione e riflessione hanno la precedenza sulla concatenzione! Esempio: <math>ab^2=abb</math> e <math>ab^R=ab</math>.
== 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 <math>L</math> un linguaggio, allora <math>L^R = \{ x | \exists y ( y \in L \land x=y^R) \}</math>
=== Concatenazione ===
La concatenazione di un linguaggio è definita come il linguaggio contenente la concatenazione delle stringhe dei linguaggi concatenati:
: <math>L'L''= \{\ xy\ |\ x\in L' \land y\in L''\ \}</math>
N.B.
* <math>L \cdot \varnothing = \varnothing \cdot L = \varnothing </math>
* <math>L \cdot \{\varepsilon\} = \{\varepsilon\} \cdot L = L </math>
=== Ripetizione o potenza ===
La ripetizione o potenza di un linguaggio viene definita ricorsivamente:
: <math>L^m = L^{m-1}L</math> per <math>m \ge 1</math>
: <math>L^0 = \{\varepsilon\}</math>
N.B. <math>\varnothing^0=\{\varepsilon\}</math>
Esempio: <math> L=\{a,b,c\} \to L^2=\{a^2,b^2,c^2,ab,ac,ba,ca,bc,cb\} \ </math>
Come visto la potenza produce un set di stringhe di dimensione fissa e finita <math>m</math>. Utilizzando la stringa vuota è possibile ottenere il set di stringhe con lunghezza minore di m.
Esempio: <math> L=\{a,b,c,\varepsilon\} \to L^2=\{a^2,b^2,c^2,ab,ac,ba,ca,bc,cb,a,b,c,\varepsilon\} \ </math>
=== Operazioni insiemistiche ===
I linguaggi godono delle classiche operazioni insiemistiche:
* <math>\cup</math>: unione (insieme composto da tutte le stringhe che compongono il primo linguaggio '''o''' il secondo linguaggio.)
* <math>\cap</math>: intersezione (insieme composto da tutte le stringhe che compongono il primo linguaggio '''e''' il secondo linguaggio.)
* <math>\setminus</math>: differenza (insieme composto da tutte le stringhe che compongono il primo linguaggio '''ma non''' il secondo linguaggio.)
* <math>\subseteq</math>: inclusione
* <math>\subset</math>: inclusione stretta
* <math>=</math>: uguaglianza
==== Definizioni ====
Definiamo '''linguaggio universale''' <math>L_{\text{universale}}</math> di un alfabeto <math>\Sigma</math> come l'insieme di tutte le stringhe di qualsiasi lunghezza sull'alfabeto:
: <math>L_{\text{universale}} = \Sigma^0 \cup \Sigma^1 \cup \Sigma^2 \cup ...</math>
Definiamo '''complemento di un linguaggio''' <math>\neg L</math> su un alfabeto <math>\Sigma</math>:
: <math>\neg L = L_{\text{universale}} \setminus L </math>
N.B.:
* <math>L_{\text{universale}} = \neg \varnothing</math>.
* 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.
: <math>L^* = \bigcup_{h=0,...,\infty} L^h = L^0 \cup L^1 \cup ... = \{\varepsilon\} \cup L^1 \cup ...</math>
Informalmente, questo insieme di stringhe è quello che è possibile generare concatenando due stringhe di L, anche con ripetizioni.
Ad esempio:
: <math>L=\{ab,ba,fg\}\ \to\ L^*=\{\varepsilon, ab, ba, fg, abab, abba,abfg, baab, baba, bafg, ...</math>
<math>L^*</math> è evidentemente sempre infinito, qualsiasi sia il linguaggio <math>L\ne \{\varepsilon\} \ne \varnothing</math>. Può capitare che <math>L=L^*</math>, ad esempio: <math>L= \{ a^n, n \ge 0 \} = L^* </math>.
N.B.: <math>L_{\text{universale}} = \Sigma^*</math>
Spesso si utilizza la sintassi <math>L \subseteq \Sigma^*</math> per dire che il linguaggio <math>L</math> è un linguaggio sull'alfabeto <math>\Sigma</math>.
==== Proprietà ====
La chiusura di Kleene gode delle seguenti proprietà:
* monotonicità: <math>L\subseteq L^*</math>
* chiusura alla concatenazione: <math>\text{if } x\in L^*\text{ and } y\in L^* \text{ allora } xy\in L^*</math>
* [[w:idempotenza|idempotenza]]: <math>(L^*)^*=L^*</math>
* commutatività con riflessione: <math>(L^*)^R = (L^R)^*</math>
* <math>\varnothing^*=\{\varepsilon\}</math>
* <math>\varepsilon^*=\{\varepsilon\}</math>
=== 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 <math>L^0</math>
: <math>L^+ = \bigcup_{h=1,...,\infty} L^h = L^1 \cup L^2 \cup ...</math>
=== Operatore quoziente ===
L'operatore quoziente, identificato dalla slash <math>L_1/L_2</math> (non backslash!). Definito come:
<math>L_1/L_2 = \{\ u\ |(\ \exists w \in L_2 | vw \in L_1L_2)\ \}</math>.
Esempio:
: <math>L_1=\{\ a^{2n}b^{2n}|n>0\ \}</math>
: <math>L_2=\{\ b^{2n+1}|n\ge 0\ \}</math>
: <math>L_1 / L_2=\{\ a^2b,a^4b, a^4b^3, ...\ \}</math>
0ubqjcekzlcowxvo5tzxpgprhlx3y1h
259742
259741
2022-08-08T10:25:03Z
151.34.228.245
/* Proprietà */
wikitext
text/x-wiki
{{risorsa|tipo=lezione|materia1=Linguaggi formali e automi|avanzamento=100%}}
== Operazioni sulle stringhe ==
=== Concatenazione ===
La concatenzione tra due stringhe, detto anche prodotto tra due stringhe, è definito come:
: siano <math>x=a_1a_2...a_h</math> e <math>y=b_1b_2...b_k</math> due stringhe, allora la loro concatenzione è <math>xy=a_1a_2...a_hb_1b_2...b_k</math>.
La concatenzione è anche indicata con <math>xy=x\cdot y</math>. Gode della proprietà associativa <math>x(yz)=(xy)z</math> e dell'additività della lunghezza <math>|xy| = |x| + |y|</math>.
Ha come [[w:elemento neutro|elemento neutro]] la stringa vuota: <math>x\varepsilon=\varepsilon x = x</math>.
=== Sottostringa ===
Diciamo che <math>y</math> è '''sottostringa''' di <math>x</math> se e solo se:
: <math>x=uyv</math> per qualche stringa <math>u</math> (detta prefisso) e <math>v</math> (detta suffisso).
<math>y</math> è sottostringa '''propria''' se e solo se <math>u \ne \varepsilon</math> e <math>v \ne \varepsilon</math>.
=== Riflessione ===
L'operazione di riflessione è definita come:
: sia <math>x=a_1a_2...a_{k-1}a_k</math> allora la sua riflessione è <math>x^R = a_ka_{k-1}...a_2a_1</math>.
Gode delle seguenti proprietà:
* riflessiva: <math>(x^R)^R=x</math>
* distributiva: <math>(xy)^R=x^R\cdot y^R</math>
* valore nullo: <math>(\varepsilon)^R=\varepsilon</math>
=== Ripetizione o potenza ===
Si definisce '''ripetizione''' o '''potenza''' di una stringa la concatenazione di se stessa <math>m</math> volte:
: <math>x^m=\underbrace{xxxx...x}_\text{m}</math> con <math>m \ge 1</math>. Se <math>m=0</math>, allora <math>x^m=x^0=\varepsilon</math>
Esempi:
* <math>x=ab\to x^5=ababababab</math>
* <math>x=\varepsilon\to x^5=\varepsilon</math>
* <math>x=ab\to x^0=\varepsilon</math>
'''N.B.''': ripetizione e riflessione hanno la precedenza sulla concatenzione! Esempio: <math>ab^2=abb</math> e <math>ab^R=ab</math>.
== 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 <math>L</math> un linguaggio, allora <math>L^R = \{ x | \exists y ( y \in L \land x=y^R) \}</math>
=== Concatenazione ===
La concatenazione di un linguaggio è definita come il linguaggio contenente la concatenazione delle stringhe dei linguaggi concatenati:
: <math>L'L''= \{\ xy\ |\ x\in L' \land y\in L''\ \}</math>
N.B.
* <math>L \cdot \varnothing = \varnothing \cdot L = \varnothing </math>
* <math>L \cdot \{\varepsilon\} = \{\varepsilon\} \cdot L = L </math>
=== Ripetizione o potenza ===
La ripetizione o potenza di un linguaggio viene definita ricorsivamente:
: <math>L^m = L^{m-1}L</math> per <math>m \ge 1</math>
: <math>L^0 = \{\varepsilon\}</math>
N.B. <math>\varnothing^0=\{\varepsilon\}</math>
Esempio: <math> L=\{a,b,c\} \to L^2=\{a^2,b^2,c^2,ab,ac,ba,ca,bc,cb\} \ </math>
Come visto la potenza produce un set di stringhe di dimensione fissa e finita <math>m</math>. Utilizzando la stringa vuota è possibile ottenere il set di stringhe con lunghezza minore di m.
Esempio: <math> L=\{a,b,c,\varepsilon\} \to L^2=\{a^2,b^2,c^2,ab,ac,ba,ca,bc,cb,a,b,c,\varepsilon\} \ </math>
=== Operazioni insiemistiche ===
I linguaggi godono delle classiche operazioni insiemistiche:
* <math>\cup</math>: unione (insieme composto da tutte le stringhe che compongono il primo linguaggio '''o''' il secondo linguaggio.)
* <math>\cap</math>: intersezione (insieme composto da tutte le stringhe che compongono il primo linguaggio '''e''' il secondo linguaggio.)
* <math>\setminus</math>: differenza (insieme composto da tutte le stringhe che compongono il primo linguaggio '''ma non''' il secondo linguaggio.)
* <math>\subseteq</math>: inclusione
* <math>\subset</math>: inclusione stretta
* <math>=</math>: uguaglianza
==== Definizioni ====
Definiamo '''linguaggio universale''' <math>L_{\text{universale}}</math> di un alfabeto <math>\Sigma</math> come l'insieme di tutte le stringhe di qualsiasi lunghezza sull'alfabeto:
: <math>L_{\text{universale}} = \Sigma^0 \cup \Sigma^1 \cup \Sigma^2 \cup ...</math>
Definiamo '''complemento di un linguaggio''' <math>\neg L</math> su un alfabeto <math>\Sigma</math>:
: <math>\neg L = L_{\text{universale}} \setminus L </math>
N.B.:
* <math>L_{\text{universale}} = \neg \varnothing</math>.
* 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.
: <math>L^* = \bigcup_{h=0,...,\infty} L^h = L^0 \cup L^1 \cup ... = \{\varepsilon\} \cup L^1 \cup ...</math>
Informalmente, questo insieme di stringhe è quello che è possibile generare concatenando due stringhe di L, anche con ripetizioni.
Ad esempio:
: <math>L=\{ab,ba,fg\}\ \to\ L^*=\{\varepsilon, ab, ba, fg, abab, abba,abfg, baab, baba, bafg, ...</math>
<math>L^*</math> è evidentemente sempre infinito, qualsiasi sia il linguaggio <math>L\ne \{\varepsilon\} \ne \varnothing</math>. Può capitare che <math>L=L^*</math>, ad esempio: <math>L= \{ a^n, n \ge 0 \} = L^* </math>.
N.B.: <math>L_{\text{universale}} = \Sigma^*</math>
Spesso si utilizza la sintassi <math>L \subseteq \Sigma^*</math> per dire che il linguaggio <math>L</math> è un linguaggio sull'alfabeto <math>\Sigma</math>.
==== Proprietà ====
La chiusura di Kleene gode delle seguenti proprietà:
* monotonicità: <math>L\subseteq L^*</math>
* chiusura alla concatenazione: <math>\text{se } x\in L^*\text{ e } y\in L^* \text{ allora } xy\in L^*</math>
* [[w:idempotenza|idempotenza]]: <math>(L^*)^*=L^*</math>
* commutatività con riflessione: <math>(L^*)^R = (L^R)^*</math>
* <math>\varnothing^*=\{\varepsilon\}</math>
* <math>\varepsilon^*=\{\varepsilon\}</math>
=== 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 <math>L^0</math>
: <math>L^+ = \bigcup_{h=1,...,\infty} L^h = L^1 \cup L^2 \cup ...</math>
=== Operatore quoziente ===
L'operatore quoziente, identificato dalla slash <math>L_1/L_2</math> (non backslash!). Definito come:
<math>L_1/L_2 = \{\ u\ |(\ \exists w \in L_2 | vw \in L_1L_2)\ \}</math>.
Esempio:
: <math>L_1=\{\ a^{2n}b^{2n}|n>0\ \}</math>
: <math>L_2=\{\ b^{2n+1}|n\ge 0\ \}</math>
: <math>L_1 / L_2=\{\ a^2b,a^4b, a^4b^3, ...\ \}</math>
pqerd74lxh3k41xmvfm1o4jl08ryitc
259743
259742
2022-08-08T11:36:50Z
Zaminex
3880
Annullate le modifiche di [[Special:Contributions/151.34.228.245|151.34.228.245]] ([[User talk:151.34.228.245|discussione]]), riportata alla versione precedente di [[User:79.22.213.240|79.22.213.240]]
wikitext
text/x-wiki
{{risorsa|tipo=lezione|materia1=Linguaggi formali e automi|avanzamento=100%}}
== Operazioni sulle stringhe ==
=== Concatenazione ===
La concatenzione tra due stringhe, detto anche prodotto tra due stringhe, è definito come:
: siano <math>x=a_1a_2...a_h</math> e <math>y=b_1b_2...b_k</math> due stringhe, allora la loro concatenzione è <math>xy=a_1a_2...a_hb_1b_2...b_k</math>.
La concatenzione è anche indicata con <math>xy=x\cdot y</math>. Gode della proprietà associativa <math>x(yz)=(xy)z</math> e dell'additività della lunghezza <math>|xy| = |x| + |y|</math>.
Ha come [[w:elemento neutro|elemento neutro]] la stringa vuota: <math>x\varepsilon=\varepsilon x = x</math>.
=== Sottostringa ===
Diciamo che <math>y</math> è '''sottostringa''' di <math>x</math> se e solo se:
: <math>x=uyv</math> per qualche stringa <math>u</math> (detta prefisso) e <math>v</math> (detta suffisso).
<math>y</math> è sottostringa '''propria''' se e solo se <math>u \ne \varepsilon</math> e <math>v \ne \varepsilon</math>.
=== Riflessione ===
L'operazione di riflessione è definita come:
: sia <math>x=a_1a_2...a_{k-1}a_k</math> allora la sua riflessione è <math>x^R = a_ka_{k-1}...a_2a_1</math>.
Gode delle seguenti proprietà:
* riflessiva: <math>(x^R)^R=x</math>
* distributiva: <math>(xy)^R=x^R\cdot y^R</math>
* valore nullo: <math>(\varepsilon)^R=\varepsilon</math>
=== Ripetizione o potenza ===
Si definisce '''ripetizione''' o '''potenza''' di una stringa la concatenazione di se stessa <math>m</math> volte:
: <math>x^m=\underbrace{xxxx...x}_\text{m}</math> con <math>m \ge 1</math>. Se <math>m=0</math>, allora <math>x^m=x^0=\varepsilon</math>
Esempi:
* <math>x=ab\to x^5=ababababab</math>
* <math>x=\varepsilon\to x^5=\varepsilon</math>
* <math>x=ab\to x^0=\varepsilon</math>
'''N.B.''': ripetizione e riflessione hanno la precedenza sulla concatenzione! Esempio: <math>ab^2=abb</math> e <math>ab^R=ab</math>.
== 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 <math>L</math> un linguaggio, allora <math>L^R = \{ x | \exists y ( y \in L \land x=y^R) \}</math>
=== Concatenazione ===
La concatenazione di un linguaggio è definita come il linguaggio contenente la concatenazione delle stringhe dei linguaggi concatenati:
: <math>L'L''= \{\ xy\ |\ x\in L' \land y\in L''\ \}</math>
N.B.
* <math>L \cdot \varnothing = \varnothing \cdot L = \varnothing </math>
* <math>L \cdot \{\varepsilon\} = \{\varepsilon\} \cdot L = L </math>
=== Ripetizione o potenza ===
La ripetizione o potenza di un linguaggio viene definita ricorsivamente:
: <math>L^m = L^{m-1}L</math> per <math>m \ge 1</math>
: <math>L^0 = \{\varepsilon\}</math>
N.B. <math>\varnothing^0=\{\varepsilon\}</math>
Esempio: <math> L=\{a,b,c\} \to L^2=\{a^2,b^2,c^2,ab,ac,ba,ca,bc,cb\} \ </math>
Come visto la potenza produce un set di stringhe di dimensione fissa e finita <math>m</math>. Utilizzando la stringa vuota è possibile ottenere il set di stringhe con lunghezza minore di m.
Esempio: <math> L=\{a,b,c,\varepsilon\} \to L^2=\{a^2,b^2,c^2,ab,ac,ba,ca,bc,cb,a,b,c,\varepsilon\} \ </math>
=== Operazioni insiemistiche ===
I linguaggi godono delle classiche operazioni insiemistiche:
* <math>\cup</math>: unione (insieme composto da tutte le stringhe che compongono il primo linguaggio '''o''' il secondo linguaggio.)
* <math>\cap</math>: intersezione (insieme composto da tutte le stringhe che compongono il primo linguaggio '''e''' il secondo linguaggio.)
* <math>\setminus</math>: differenza (insieme composto da tutte le stringhe che compongono il primo linguaggio '''ma non''' il secondo linguaggio.)
* <math>\subseteq</math>: inclusione
* <math>\subset</math>: inclusione stretta
* <math>=</math>: uguaglianza
==== Definizioni ====
Definiamo '''linguaggio universale''' <math>L_{\text{universale}}</math> di un alfabeto <math>\Sigma</math> come l'insieme di tutte le stringhe di qualsiasi lunghezza sull'alfabeto:
: <math>L_{\text{universale}} = \Sigma^0 \cup \Sigma^1 \cup \Sigma^2 \cup ...</math>
Definiamo '''complemento di un linguaggio''' <math>\neg L</math> su un alfabeto <math>\Sigma</math>:
: <math>\neg L = L_{\text{universale}} \setminus L </math>
N.B.:
* <math>L_{\text{universale}} = \neg \varnothing</math>.
* 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.
: <math>L^* = \bigcup_{h=0,...,\infty} L^h = L^0 \cup L^1 \cup ... = \{\varepsilon\} \cup L^1 \cup ...</math>
Informalmente, questo insieme di stringhe è quello che è possibile generare concatenando due stringhe di L, anche con ripetizioni.
Ad esempio:
: <math>L=\{ab,ba,fg\}\ \to\ L^*=\{\varepsilon, ab, ba, fg, abab, abba,abfg, baab, baba, bafg, ...</math>
<math>L^*</math> è evidentemente sempre infinito, qualsiasi sia il linguaggio <math>L\ne \{\varepsilon\} \ne \varnothing</math>. Può capitare che <math>L=L^*</math>, ad esempio: <math>L= \{ a^n, n \ge 0 \} = L^* </math>.
N.B.: <math>L_{\text{universale}} = \Sigma^*</math>
Spesso si utilizza la sintassi <math>L \subseteq \Sigma^*</math> per dire che il linguaggio <math>L</math> è un linguaggio sull'alfabeto <math>\Sigma</math>.
==== Proprietà ====
La chiusura di Kleene gode delle seguenti proprietà:
* monotonicità: <math>L\subseteq L^*</math>
* chiusura alla concatenazione: <math>\text{if } x\in L^*\text{ and } y\in L^* \text{ then } xy\in L^*</math>
* [[w:idempotenza|idempotenza]]: <math>(L^*)^*=L^*</math>
* commutatività con riflessione: <math>(L^*)^R = (L^R)^*</math>
* <math>\varnothing^*=\{\varepsilon\}</math>
* <math>\varepsilon^*=\{\varepsilon\}</math>
=== 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 <math>L^0</math>
: <math>L^+ = \bigcup_{h=1,...,\infty} L^h = L^1 \cup L^2 \cup ...</math>
=== Operatore quoziente ===
L'operatore quoziente, identificato dalla slash <math>L_1/L_2</math> (non backslash!). Definito come:
<math>L_1/L_2 = \{\ u\ |(\ \exists w \in L_2 | vw \in L_1L_2)\ \}</math>.
Esempio:
: <math>L_1=\{\ a^{2n}b^{2n}|n>0\ \}</math>
: <math>L_2=\{\ b^{2n+1}|n\ge 0\ \}</math>
: <math>L_1 / L_2=\{\ a^2b,a^4b, a^4b^3, ...\ \}</math>
kfyiu2jkvvwjiurjz7x9op5vv7dajdg