Stella di Kleene
La stella di Kleene , a volte chiamata chiusura Kleene o chiusura iterativa, è nella teoria del linguaggio , un operatore unario usato per descrivere i linguaggi formali . Il nome stella deriva dalla notazione usata, un asterisco , e Kleene da Stephen Cole Kleene che lo ha introdotto.
La stella di Kleene è uno dei tre operatori di base utilizzati per definire un'espressione regolare , insieme a concatenazione e unione di insiemi .
Applicato a un set , risulta in language , definito come:
X{\ stile di visualizzazione X}
X*{\ stile di visualizzazione X ^ {*}}![X^ {*}](https://wikimedia.org/api/rest_v1/media/math/render/svg/01924e6e5570e2631081fea6c6981b4872d3e04b)
- Se è un alfabeto , cioè un insieme di simboli o caratteri, allora l'insieme di parole è sopra , parola vuota inclusa.X{\ stile di visualizzazione X}
X*{\ stile di visualizzazione X ^ {*}}
X{\ stile di visualizzazione X}
ε{\ displaystyle \ varepsilon}![\ varepsilon](https://wikimedia.org/api/rest_v1/media/math/render/svg/a30c89172e5b88edbd45d3e2772c7f5e562e5173)
- Se è una lingua , allora è la lingua più piccola che la contiene, che contiene e che è stabile per concatenazione .X{\ stile di visualizzazione X}
X*{\ stile di visualizzazione X ^ {*}}
ε{\ displaystyle \ varepsilon}![\ varepsilon](https://wikimedia.org/api/rest_v1/media/math/render/svg/a30c89172e5b88edbd45d3e2772c7f5e562e5173)
Esempi
Per l'alfabeto , abbiamo
{a,b,vs}{\ displaystyle \ {a, b, c \}}![\{ABC\}](https://wikimedia.org/api/rest_v1/media/math/render/svg/75e9bc621ced3f02e87b1c40be37867929142bf4)
{a,b,vs}*={ε,a,b,vs,aa,ab,avs,ba,bb,bvs,vsa,vsb,vsvs,aaa,...}{\ displaystyle \ {a, b, c \} ^ {*} = \ {\ varepsilon, a, b, c, aa, ab, ac, ba, bb, bc, ca, cb, cc, aaa, \ ldots \}}![\ {a, b, c \} ^ {*} = \ {\ varepsilon, a, b, c, aa, ab, ac, ba, bb, bc, ca, cb, cc, aaa, \ ldots \}](https://wikimedia.org/api/rest_v1/media/math/render/svg/043873f9c32f47897c270f7df86e580f24464d30)
Per la parte composta dalle due parole e sull'alfabeto si ottiene
X={aa,b}{\ displaystyle X = \ {aa, b \}}
aa{\ displaystyle aa}
b{\ stile di visualizzazione b}
{a,b}{\ displaystyle \ {a, b \}}![\ {a, b \}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8127b44bf0e5a64fdc9301e188852ab9b97a1fe8)
{aa,b}*={ε,b,aa,bb,aab,baa,bbb,aaaa,aabb,baab,bbaa,bbbb,...}{\ displaystyle \ {aa, b \} ^ {*} = \ {\ varepsilon, b, aa, bb, aab, baa, bbb, aaaa, aabb, baab, bbaa, bbbb, \ ldots \}}![\ {aa, b \} ^ {*} = \ {\ varepsilon, b, aa, bb, aab, baa, bbb, aaaa, aabb, baab, bbaa, bbbb, \ ldots \}](https://wikimedia.org/api/rest_v1/media/math/render/svg/edec0b8236f3980ea047b17c74e3b8ac74346ebe)
Definizione
Chiamiamo la stella di Kleene di una parte di un monoide il submonoide generato da . Questo submonoide è notato . Come di consueto per le operazioni di chiusura, può essere definita in tre modi equivalenti:
X{\ stile di visualizzazione X}
M{\ stile di visualizzazione M}
X{\ stile di visualizzazione X}
X*{\ stile di visualizzazione X ^ {*}}![X^ {*}](https://wikimedia.org/api/rest_v1/media/math/render/svg/01924e6e5570e2631081fea6c6981b4872d3e04b)
-
X*{\ stile di visualizzazione X ^ {*}}
è la parte più piccola del contenitore e l'elemento neutro e chiuso per il funzionamento di .M{\ stile di visualizzazione M}
X{\ stile di visualizzazione X}
M{\ stile di visualizzazione M}
M{\ stile di visualizzazione M}![M](https://wikimedia.org/api/rest_v1/media/math/render/svg/f82cade9898ced02fdd08712e5f0c0151758a0dd)
-
X*{\ stile di visualizzazione X ^ {*}}
è l'intersezione di tutti i submonoidi che lo contengono .M{\ stile di visualizzazione M}
X{\ stile di visualizzazione X}![X](https://wikimedia.org/api/rest_v1/media/math/render/svg/68baa052181f707c662844a465bfeeb135e82bab)
-
X*{\ stile di visualizzazione X ^ {*}}
è l'insieme di tutti i prodotti della forma , per e .X1X2⋯Xnon{\ displaystyle x_ {1} x_ {2} \ cdots x_ {n}}
non≥0{\ displaystyle n \ geq 0}
X1,X2,...,Xnon∈X{\ displaystyle x_ {1}, x_ {2}, \ ldots, x_ {n} \ in X}![x_ {1}, x_ {2}, \ ldots, x_ {n} \ in X](https://wikimedia.org/api/rest_v1/media/math/render/svg/1de7ed4f897d271681a22cd47c68694e25955cf9)
Se è un gruppo elettrogeno del monoide , abbiamo in particolare .
X{\ stile di visualizzazione X}
M{\ stile di visualizzazione M}
X*=M{\ stile di visualizzazione X ^ {*} = M}![X ^ {*} = M](https://wikimedia.org/api/rest_v1/media/math/render/svg/fea4bb899d2eb205c340d96434875a8861052e8f)
Caso del monoide libero
Nel caso di un alfabeto , indichiamo l'insieme di tutte le parole su . L'insieme è un monoide per la concatenazione , ed è generato da (per essere abbastanza rigorosi, è generato dalle parole composte da una lettera, che identifichiamo con le lettere).
A{\ stile di visualizzazione A}
A*{\ stile di visualizzazione A ^ {*}}
A{\ stile di visualizzazione A}
A*{\ stile di visualizzazione A ^ {*}}
A{\ stile di visualizzazione A}
A*{\ stile di visualizzazione A ^ {*}}![A ^ {*}](https://wikimedia.org/api/rest_v1/media/math/render/svg/44e23745a51c2c2d8d91fd98c1cf721573747ece)
Se è una parte di , allora è un submonoide di cui può o meno essere libero. Si è soliti nota l'intera
X{\ stile di visualizzazione X}
A*{\ stile di visualizzazione A ^ {*}}
X*{\ stile di visualizzazione X ^ {*}}
A*{\ stile di visualizzazione A ^ {*}}
Xnon{\ stile di visualizzazione X ^ {n}}![X^ {n}](https://wikimedia.org/api/rest_v1/media/math/render/svg/268db8293666fefd75cfb00513706171948edf09)
Xnon={X1X2⋯Xnon|X1,X2,...,Xnon∈X}{\ displaystyle X ^ {n} = \ {x_ {1} x_ {2} \ cdots x_ {n} \ mid x_ {1}, x_ {2}, \ ldots, x_ {n} \ in X \}}![X ^ {n} = \ {x_ {1} x_ {2} \ cdots x_ {n} \ mid x_ {1}, x_ {2}, \ ldots, x_ {n} \ in X \}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0619e87825f65be6b1a2feb7859458815f916da8)
di tutti gli articoli prodotti . Abbiamo quindi la formula
non{\ stile di visualizzazione n}
X{\ stile di visualizzazione X}![X](https://wikimedia.org/api/rest_v1/media/math/render/svg/68baa052181f707c662844a465bfeeb135e82bab)
X*=⋃non≥0Xnon{\ displaystyle X ^ {*} = \ bigcup _ {n \ geq 0} X ^ {n}}![X ^ {*} = \ bigcup _ {{n \ geq 0}} X ^ {n}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0e766f13ec6a5ef2e0bd1ff059b3b7446c7dcc4c)
.
If è un submonoide generato liberamente , cioè se ogni parola di
è prodotta in modo univoco da parole di , diciamo che è un codice o che è una base di .
X*{\ stile di visualizzazione X ^ {*}}
X{\ stile di visualizzazione X}
X*{\ stile di visualizzazione X ^ {*}}
X{\ stile di visualizzazione X}
X{\ stile di visualizzazione X}
X{\ stile di visualizzazione X}
X*{\ stile di visualizzazione X ^ {*}}![X^ {*}](https://wikimedia.org/api/rest_v1/media/math/render/svg/01924e6e5570e2631081fea6c6981b4872d3e04b)
Ad esempio, l'insieme è un codice e l'insieme non è un codice perché la parola ha entrambe le fattorizzazioni
X={aa,b}{\ displaystyle X = \ {aa, b \}}
X={a,ab,ba}{\ displaystyle X = \ {a, ab, ba \}}
aba{\ displaystyle aba}![aba](https://wikimedia.org/api/rest_v1/media/math/render/svg/bfc6a0b7eaf6b60d8d3e6cdc5b75e057d9a1ed03)
aba = ab . un = un . ba .
Operatore più
L' operatore più , chiamato anche stella propria o stella positiva , è un operatore analogo alla stella di Kleene. Associa a una parte di un semigruppo il sottogruppo generato da , notato . Abbiamo
X{\ stile di visualizzazione X}
M{\ stile di visualizzazione M}
X{\ stile di visualizzazione X}
X+{\ stile di visualizzazione X ^ {+}}![X^ {+}](https://wikimedia.org/api/rest_v1/media/math/render/svg/18e0e7c566b554eafc1b5705551ac4e939074777)
X+=⋃non>0Xnon{\ displaystyle X ^ {+} = \ bigcup _ {n> 0} X ^ {n}}![X ^ {+} = \ bigcup _ {{n> 0}} X ^ {n}](https://wikimedia.org/api/rest_v1/media/math/render/svg/43656e0df731581e82b5c1ab344b8d3b2ee45b70)
.
Come di consueto per la stella, l'operatore più può essere definito in tre modi equivalenti:
-
X+{\ stile di visualizzazione X ^ {+}}
è la parte più piccola del contenitore e chiusa per il funzionamento di .M{\ stile di visualizzazione M}
X{\ stile di visualizzazione X}
M{\ stile di visualizzazione M}![M](https://wikimedia.org/api/rest_v1/media/math/render/svg/f82cade9898ced02fdd08712e5f0c0151758a0dd)
-
X+{\ stile di visualizzazione X ^ {+}}
è l'intersezione di tutti i sottogruppi contenenti .M{\ stile di visualizzazione M}
X{\ stile di visualizzazione X}![X](https://wikimedia.org/api/rest_v1/media/math/render/svg/68baa052181f707c662844a465bfeeb135e82bab)
-
X+{\ stile di visualizzazione X ^ {+}}
è l'insieme di tutti i prodotti della forma , per e .X1X2⋯Xnon{\ displaystyle x_ {1} x_ {2} \ cdots x_ {n}}
non>0{\ stile di visualizzazione n> 0}
X1,X2,...,Xnon∈X{\ displaystyle x_ {1}, x_ {2}, \ ldots, x_ {n} \ in X}![x_ {1}, x_ {2}, \ ldots, x_ {n} \ in X](https://wikimedia.org/api/rest_v1/media/math/render/svg/1de7ed4f897d271681a22cd47c68694e25955cf9)
In un monoide, abbiamo le seguenti relazioni tra la stella e l'operatore più:
X*=X+∪{ε}, X+=XX*=X*X.{\ displaystyle X ^ {*} = X ^ {+} \ tazza \ {\ varepsilon \}, \ X ^ {+} = XX ^ {*} = X ^ {*} X.}![{\ displaystyle X ^ {*} = X ^ {+} \ tazza \ {\ varepsilon \}, \ X ^ {+} = XX ^ {*} = X ^ {*} X.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b47d86bdd3931b5bfb972fe26250f9fddbbb3ac6)
.
I rapporti tra la stella e la stella positiva sono stati oggetto di numerose presentazioni; uno dei più completi è di Brzozowski , Grant e Shallit
Ripetizione e complementazione delle stelle
Le due operazioni sui linguaggi formali che sono la stella (positiva o no) e il passaggio al complemento hanno notevoli proprietà algebriche: la prima è idempotente poiché per qualsiasi lingua e la seconda è involutiva poiché in effetti il complemento del complemento di una lingua è la lingua di partenza.
(L*)*=L*{\ stile di visualizzazione (L ^ {*}) ^ {*} = L ^ {*}}
L{\ stile di visualizzazione L}![L](https://wikimedia.org/api/rest_v1/media/math/render/svg/103168b86f781fe6e9a4a87b8ea1cebe0ad4ede8)
La ripetizione di queste due operazioni, da una data lingua , non produce un'infinità di lingue, ma un numero finito. Questo fenomeno, osservato da David Peleg nel 1984, è da mettere in relazione con un già vecchio risultato topologico di Kuratowski , il teorema di chiusura/complementare di Kuratowski .
L{\ stile di visualizzazione L}![L](https://wikimedia.org/api/rest_v1/media/math/render/svg/103168b86f781fe6e9a4a87b8ea1cebe0ad4ede8)
Per dimostrare l'asserzione, consideriamo quindi le due operazioni
L↦L*{\ displaystyle L \ mapsto L ^ {*}}![{\ displaystyle L \ mapsto L ^ {*}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8a982d3902578c08ba60152adc47203627d2b018)
e
L↦L-{\ displaystyle L \ mapsto L ^ {-}}
stella e complemento. Queste operazioni sono scritte in notazione postfissa. Abbiamo in particolare
L**=L*{\ stile di visualizzazione L ^ {**} = L ^ {*}}![{\ stile di visualizzazione L ^ {**} = L ^ {*}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/71dcb3f1e21a5cc9d31b3e60a2c1e8778a317b03)
(idempotenza) e (involuzione).
L--=L{\ stile di visualizzazione L ^ {-} = L}![{\ stile di visualizzazione L ^ {-} = L}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d2cc01f4d8539b0b0910c773e411131d8441314a)
Una serie di operazioni può quindi sempre essere semplificata sostituendo successive operazioni uguali, e si è ricondotti ad un'alternanza di stelle e complementi. La proposta nasce dall'identità
L*-*-*-*=L*-*{\ displaystyle L ^ {* - * - * - *} = L ^ {* - *}}![{\ displaystyle L ^ {* - * - * - *} = L ^ {* - *}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3603ed2c738fc35ad4eb4b48e454b8f6a3c036fd)
che dice che una sequenza di 8 operazioni può essere sostituita da una sequenza di sole 4 operazioni (tenendo conto del fatto che una sequenza può iniziare o finire con una complementazione).
Dimostrazione
Per dimostrare questa formula, mostriamo prima l'inclusione
L*-*-*⊆L*(1){\ displaystyle L ^ {* - * - *} \ subseteq L ^ {*} \ qquad (1)}![{\ displaystyle L ^ {* - * - *} \ subseteq L ^ {*} \ qquad (1)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d2235573b91ebda66118cca0e3701092ae47d227)
.
Questa inclusione si ottiene partendo da
L*-⊆L*-*{\ displaystyle L ^ {* -} \ subseteq L ^ {* - *}}![{\ displaystyle L ^ {* -} \ subseteq L ^ {* - *}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4e40bda2935c790bac219ff1e6130f5340ecb7d2)
,
poi, passando al complementare:
L*--=L*⊇L*-*-{\ displaystyle L ^ {* -} = L ^ {*} \ supseteq L ^ {* - * -}}![{\ displaystyle L ^ {* -} = L ^ {*} \ supseteq L ^ {* - * -}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f4afa625b0d7b11955f93492775259b5f509c54a)
,
e infine, applicando la stella
L**=L*⊇L*-*-*{\ displaystyle L ^ {**} = L ^ {*} \ supseteq L ^ {* - * - *}}![{\ displaystyle L ^ {**} = L ^ {*} \ supseteq L ^ {* - * - *}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2f98354dc28ba9715733f72475ad950ed7f9c1f1)
.
L'equazione (1) dà, applicando il complemento poi la stella:
L*-*-*-*⊇L*-*{\ displaystyle L ^ {* - * - * - *} \ supseteq L ^ {* - *}}![{\ displaystyle L ^ {* - * - * - *} \ supseteq L ^ {* - *}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0c79dbf973d406dd7f1abeb37eedcc262e209196)
.
D'altra parte, sostituendo per nell'equazione (1), si ottiene:
L*-{\ stile di visualizzazione L ^ {* -}}
L{\ stile di visualizzazione L}![L](https://wikimedia.org/api/rest_v1/media/math/render/svg/103168b86f781fe6e9a4a87b8ea1cebe0ad4ede8)
L*-*-*-*⊆L*-*{\ displaystyle L ^ {* - * - * - *} \ subseteq L ^ {* - *}}![{\ displaystyle L ^ {* - * - * - *} \ subseteq L ^ {* - *}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2a59b9635e374aa75270b2546eda46792a0b3f6c)
.
Le due disuguaglianze danno il risultato desiderato.
Le estensioni sono presentate nell'articolo di Brzozowski, Grant e Shallit già citato.
Caso di linguaggi razionali
I linguaggi regolari o regolari sono descritti da espressioni regolari , di cui Kleene star è coinvolta in modo essenziale: è lei che ha passato le infinite lingue. La corrispondente costruzione sugli automi finiti deterministici passa attraverso un passaggio intermedio utilizzando un automa finito non deterministico . Se l' automa minimo che riconosce il linguaggio ha affermazioni deterministiche minime, l'automa finito che riconosce può, in linea di principio, agli stati. Ora, è noto da tempo che questo numero di stati è al massimo , e anche, più precisamente, al massimo , dove è il numero di stati terminali che non sono stato iniziale. È possibile un intero set di valori intermedi.
L{\ stile di visualizzazione L}
non{\ stile di visualizzazione n}
L*{\ stile di visualizzazione L ^ {*}}
2non{\ stile di visualizzazione 2 ^ {n}}
3/4⋅2non{\ displaystyle 3/4 \ cdot 2 ^ {n}}
2non-1+2non-1-K{\ stile di visualizzazione 2 ^ {n-1} + 2 ^ {n-1-k}}
K{\ stile di visualizzazione k}![K](https://wikimedia.org/api/rest_v1/media/math/render/svg/c3c9a2c7b599b37105512c5d570edc034056dd40)
Una parola stella
La famiglia delle lingue formali ottenute, dalle lingue che sono la stella di una parola, dalle operazioni di chiusura booleane è una famiglia abbastanza ristretta. Ammette un'efficace caratterizzazione equazionale, che permette di decidere se una data lingua appartiene a questa famiglia.
Note e riferimenti
-
Janusz Brzozowski , Elyot di Grant e Jeffrey Shallit , “ Chiusure in linguaggi formali e Kuratowski del teorema ”, International Journal of Fondamenti di Informatica , vol. 22, n . 02,2011, pag. 301-321 ( ISSN 0129-0541 , DOI 10.1142/S0129054111008052 , arXiv 0901.3761 )
-
David Peleg , " Una chiusura generalizzata e un fenomeno del complemento " , Discrete Mathematics , vol. 50,1984, pag. 285-293 ( ISSN 0012-365X , DOI 10.1016 / 0012-365X (84) 90055-4 , leggi online ).
-
Peleg 1984 , Lemma 3.1.
-
Matúš Palmovský, “ Chiusura di Kleene e complessità dello stato ”, RAIRO-Theor. Inf. Appl. , vol. 50,2016, pag. 251–261 ( DOI 10.1051 / ita / 2016024 ).
-
Laure Daviaud e Charles Paperman , “ Classi di linguaggi generati dalla stella di Kleene di una parola ”, Informazione e calcolo , vol. 262,2018, pag. 90–109 ( ISSN 0890-5401 , DOI 10.1016 / j.ic.2018.07.002 ).
Bibliografia
- (it) Stephen C. Kleene , "Rappresentazione di eventi in reti nervose e automi finiti" , in Claude E. Shannon e John McCarthy (a cura di), Automata Studies , Princeton, Princeton University Press, coll. "Annali di studi matematici" ( n o 34),1956, viii + 285 p. ( ISBN 978-0691079165 ) , pag. 3-41
- Jacky Akoka e Isabelle Comyn-Wattiau (a cura di), Encyclopedia of Computing and Information Systems , Paris, Vuibert ,2006, xxxv + 1941 p. ( ISBN 978-2-7117-4846-4 )
- Olivier Carton, Linguaggi formali, computabilità e complessità: laurea triennale e magistrale in matematica o informatica, opzione informatica dell'aggregazione matematica , Paris, Vuibert ,2008, 237 pag. ( ISBN 978-2-7117-2077-4 , presentazione online )
- Jacques Sakarovitch , Elementi di teoria degli automi , Vuibert ,2003, 816 pag. ( ISBN 978-2-7117-4807-5 )
Vedi anche
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">