Kleene tétele
Az elméleti informatikában , pontosabban az automata-elméletben , Kleene-tétel azt állítja, hogy a nyelv racionális (azaz szabályos kifejezéssel írható le ) csak akkor, ha azt egy véges automata felismeri . A formális nyelvek és automaták elméletének alapvető tétele. Ennek a tételnek az első megfogalmazása Stephen C. Kleene matematikusnak köszönhető .
Történelmi
A véges automaták kezdetét, és különösen Kleene-tétel keletkezését Dominique Perrin írta le. A véges automaták első említése egy McCulloch és Pitts 1943-as cikkéből származik . Stephen Kleene vette át ezt a cikket 1956-ban, és bemutatta tételének első bizonyítékát. Az első teljes beszámolót Rabin és Scott adja 1959-ben.
Kortárs megfogalmazás
Eilenberg értekezése óta Kleene tétele tömörebben a következőképpen fogalmazódik meg.
Az ábécé fölötti racionális nyelvek halmaza definíció szerint a legkisebb részhalmaz, amely a szinguletteket (az egyetlen elemre redukált részeket) és az üres halmazt tartalmazza, és amelyet az unió, a szorzat és a csillag művelete zár le . Ezt a készletet tudomásul veszik .
NÁL NÉL{\ displaystyle A}NÁL NÉL∗{\ displaystyle A ^ {*}}Patkány NÁL NÉL∗{\ displaystyle {\ text {Rat}} A ^ {*}}
Hívjuk felismerhető nyelv ábécére olyan nyelv, amely lehet felismerni egy véges automata on . Megjegyezzük a felismerhető nyelvek halmazát .
NÁL NÉL{\ displaystyle A}NÁL NÉL{\ displaystyle A}Rec NÁL NÉL∗{\ displaystyle {\ text {Rec}} A ^ {*}}
Ezután Kleene tételét a következőképpen fogalmazzuk meg.
Kleene-tétel - A véges ábécén egyenlőség áll fenn a racionális nyelvek és a felismerhető nyelvek között. Más szavakkal, van
NÁL NÉL{\ displaystyle A}
Patkány NÁL NÉL∗=Rec NÁL NÉL∗{\ displaystyle {\ text {Rat}} A ^ {*} = {\ text {Rec}} A ^ {*}}
Tüntetések
Ennek a tételnek sokféle bizonyítási változata létezik. A bizonyítások többsége konstruktív, vagyis olyan algoritmusokat adunk meg, amelyek egy reguláris kifejezésből egy automatát, az automatából pedig egy reguláris kifejezést számolnak.
Befogadás Patkány NÁL NÉL∗⊂Rec NÁL NÉL∗{\ displaystyle {\ text {Patkány}} A ^ {*} \ részhalmaz {\ text {Rec}} A ^ {*}}
- Megmutatjuk, hogy a beállított felismerhető nyelvek lezárjuk műveleteinek unió, a termék és a csillag által végző szerkezetek a megfelelő automata (lásd a bekezdés építése véges automaták rendszeres kifejezést a cikk nem determinisztikus véges automata ) ; mivel tartalmazza a szinguletteket és az üres halmazt is, a .Patkány NÁL NÉL∗{\ displaystyle {\ text {Rat}} A ^ {*}}
- Bizonyítjuk, hogy a szabályos kifejezéssel leírt nyelveket egy véges automata felismeri . A legnépszerűbb módszerek:
A gyakorlati alkalmazások felkeltették az érdeklődést a hatékony algoritmusok kifejlesztése iránt, hogy megvalósítsák a bizonyításba beavatkozó konstrukciókat.
Befogadás Rec NÁL NÉL∗⊂Patkány NÁL NÉL∗{\ displaystyle {\ text {Rec}} A ^ {*} \ subset {\ text {Rat}} A ^ {*}}
Kérdés, hogy szabályos kifejezést adjunk a véges automata által felismert nyelv számára. Három algoritmus közös:
Mindezek az állapotok eliminációs módszerei.
Általánosítások és kiterjesztések
Kleene-Schützenberger-tétel
Marcel-Paul Schützenberger matematikusnak köszönhetjük Kleene tételének kiterjesztését a formális sorokra (illetve a súlyozott automatákra ). A tétel azt állítja, hogy a nem-kommutatív változók formális sorozata egy félgyűrű együtthatóival akkor és csak akkor racionális, ha azt egy súlyozott véges automata felismeri, amelynek a címkék megfelelő súlyai ennek a félgyűrűnek az elemei.
A monoidok kiterjesztése
Kleene tételét megpróbálták kiterjeszteni általános, nem feltétlenül szabad monoidokra. Adott egy monoid , a racionális részei az a legkisebb család részei tartalmazó singletons és az üres halmaz, és lezárt unió, a termék és a folyosón, hogy a generált submonoid (az analóg Kleene csillaga a monoids). A racionális részek halmazát jelöljük .
M{\ displaystyle M}M{\ displaystyle M}M{\ displaystyle M}Patkány M{\ displaystyle {\ text {Rat}} M}M{\ displaystyle M}
A monoid felismerhető részének fogalmát algebrailag kell kifejezni. A monoid egy része felismerhető része annak, ha véges index-kongruencia telíti el, más szóval, ha van véges monoid , és egy olyan szurjektív morfizmus, mint például , ahol . A felismerhető részek halmazát jelöljük .
H{\ displaystyle H}M{\ displaystyle M}M{\ displaystyle M} NEM{\ displaystyle N}f:M→NEM{\ displaystyle f: M \ - N}H=f-1(K){\ displaystyle H = f ^ {- 1} (K)}H=f(H){\ displaystyle H = f (H)}Rec M{\ displaystyle {\ text {Rec}} M}M{\ displaystyle M}
Ezekkel a definíciókkal az egyenlőség igaz például a véges monoidokban. McKnight bebizonyította, hogy ha végesen generált monoid, akkor . Az egyenlőség általában nem igaz. Különösen két szabad monoid termékében a racionális részek a racionális transzdukciók, míg a felismerhető részek a Mezei-tétel szerint a két komponens monoid felismerhető részeinek termékeinek véges egyesülései.
Rec M=Patkány M{\ displaystyle {\ text {Rec}} M = {\ text {Rat}} M}M{\ displaystyle M}Rec M⊂Patkány M{\ displaystyle {\ text {Rec}} M \ subset {\ text {Rat}} M}
A csoportok esete
A csoport alcsoportja akkor és csak akkor ismerhető fel, ha véges indexű.
H{\ displaystyle H}G{\ displaystyle G}G{\ displaystyle G}
A csoport egy alcsoportja akkor és csak akkor ésszerű része, ha véglegesen generálódik.
H{\ displaystyle H}G{\ displaystyle G}G{\ displaystyle G}
Ha maga is végesen generálódik, akkor a McKnight fent idézett tétele azt sugallja, hogy bármely véges index alcsoport végesen generálódik, ezt az eredményt általában Howsonnak tulajdonítják.
G{\ displaystyle G}
Kleene tételei részben kommutatív monoidokra
Kleene tétele továbbra is érvényes marad, Kleene csillagának korlátozása mellett,
szabad nyomú monoidokban vagy részben kommutatív monoidokban.
Legyen ábécé. Egy függetlenség kapcsolata , vagy kapcsolási kapcsolat része az , amely irreflexive és szimmetrikus. A kapcsolat a függetlenség határozza meg viszonyát reflexív és szimmetrikus függőség által , és fordítva.
NÁL NÉL{\ displaystyle A} én{\ displaystyle I}én{\ displaystyle I}NÁL NÉL×NÁL NÉL{\ displaystyle A \ times A}én{\ displaystyle I}D{\ displaystyle D}D=NÁL NÉL×NÁL NÉL∖én{\ displaystyle D = A \ szor A \ setminus I}
A függetlenségi viszony bináris relációt indukál arra , hogy hol és csak akkor és csak szavakra és párra . A reflexív, szimmetrikus és transzitív lezárással jelöljük . A nyomok monoidja a monoid hányadosa . A elemei vannak nyomok . Egy szóhoz vagy nyomhoz az összes betűt feljegyezzük . Két nyomok és a független , ha bármely levél ingázik minden levél . A nyom akkor kapcsolódik, ha olyan részgráfot indukál, amelynek csúcsai a betűk, az élei pedig az elemei .
∼{\ displaystyle \ sim}NÁL NÉL∗{\ displaystyle A ^ {*}}u∼v{\ displaystyle u \ sim v}u=xnál nélby{\ displaystyle u = xaby}v=xbnál nély{\ displaystyle v = xbay}x,y∈NÁL NÉL∗{\ displaystyle x, y \ A ^ -ban {*}}(nál nél,b)∈én{\ displaystyle (a, b) \ I-ben}≡{\ displaystyle \ equiv}∼{\ displaystyle \ sim}NÁL NÉL∗/≡{\ displaystyle A ^ {*} / {\ equiv}}NÁL NÉL∗/≡{\ displaystyle A ^ {*} / {\ equiv}}w{\ displaystyle w}alph(w){\ displaystyle {\ text {alph}} (w)}w{\ displaystyle w}u{\ displaystyle u}v{\ displaystyle v}u{\ displaystyle u}v{\ displaystyle v}u{\ displaystyle u}alph(u){\ displaystyle {\ text {alph}} (u)}D{\ displaystyle D}
A csillag versengő Kleene ( versenyző csillag angolul) egy részének a halmaza , amely az összes kapcsolódó nem üres pálya, hogy ingázik a nyoma . Jelölje a szinglettek és az üres halmaz legkisebb részhalmazát, amelyeket az unió, a termék és a versengő Kleene-csillag művelete zár le. Ezután Ochmański miatt a következő egyenlőség áll rendelkezésünkre:
x{\ displaystyle X}NÁL NÉL∗/≡{\ displaystyle A ^ {*} / {\ equiv}}(vs.(x))∗{\ displaystyle (c (X)) ^ {*}}vs.(x){\ displaystyle c (X)}x{\ displaystyle X}Patkányvs.(NÁL NÉL∗/≡){\ displaystyle {\ text {Rat}} ^ {c} (A ^ {*} / {\ equiv})}NÁL NÉL∗/≡{\ displaystyle A ^ {*} / {\ equiv}}
Patkányvs.(NÁL NÉL∗/≡) = Rec(NÁL NÉL∗/≡).{\ displaystyle {\ text {Rat}} ^ {c} (A ^ {*} / {\ equiv}) \ = \ {\ text {Rec}} (A ^ {*} / {\ equiv}).}Megjegyzések
-
Kleene (1956)
-
Perrin (1995)
-
McCullogh és Pitts (1943)
-
Rabin és Scott (1959)
-
Eilenberg (1984)
-
lásd Sakarovich (2003)
-
A kiterjesztések és változatai, lásd Droste et al. (2009)
-
Ez a bekezdés Diekert és Métivier (1997) cikkéből származik .
Cikkek
- Warren S. McCulloch és Walter Pitts , „ Az idegi tevékenységben immanens ötletek logikus kalkulusa ”, Bull. Math. Biophys. , vol. 5,1943, P. 115-133
- Robert McNaughton és H. Yamada, „ Regular Expressions and State Graphs for Automata ”, IEEE Transactions on Electronic Computers , 1. évf. 9, n o 1,1960, P. 39-47
- Stephen C. Kleene: „ Események ábrázolása ideghálókban és véges automatákban. Automata Studies " Annals of Mathematics Studies , Princeton University Press, n o 34,1956, P. 3-41
- Dominique Perrin, " Az automaták elméletének kezdetei ", Számítástechnika és tudomány , vol. 14, n o 4,1995, P. 409-433 ( online olvasás )
- Michael O. Rabin és Dana Scott, „ Véges automaták és döntési problémáik ”, IBM J. Res. Fejleszteni. , vol. 3,1959, P. 114-125
- Michaël Cadilhac, Dmitry Chistikov és Georg Zetzsche, „A Baumslag-Solitar Groups Rational Subsets” , in Artur Czumaj Anuj Dawar Emanuela Merelli (szerkesztők), Proceedings of ICALP 2020 , Schloss Dagstuhl - Leibniz-Zentrum für Informatik, coll. "LIPIcs" ( n ° 168)2020( DOI 10.4230 / LIPIcs.ICALP.2020.116 , arXiv 2006.11898 (részletes változat) , online olvasható ) , p. 116: 1-116: 16
Bibliográfia
- Olivier Carton , hivatalos nyelvek, kiszámíthatóság és összetettség ,2008[ a kiadás részlete ] ( online olvasható )
- (en) Volker Diekert és Yves Métivier , „Részleges kommutáció és nyomok” , G. Rozenberg, A. Salomaa (szerkesztők), Formális nyelvek kézikönyve , vol. 3: A szavakon túl , Springer Verlag,1997( ISBN 978-3-5406-0649-9 )
- en) Manfred Droste, Werner Kuich és Heiko Vogler, Súlyozott automaták kézikönyve , Springer-Verlag ,2009, 608 p. ( ISBN 978-3-642-01491-8 )
- en) Samuel Eilenberg, Automata, Languages and Machines, Vol. A , New York, Academic Press ,1974( ISBN 978-0-12-234001-7 )
-
Jacques Sakarovitch, Az automaták elméletének elemei , Vuibert ,2003, 816 p. ( ISBN 978-2-7117-4807-5 )Angol fordítás javításokkal: Elemei az automaták elméletéhez , Cambridge University Press 2009, ( ISBN 978-0-52184425-3 )
Kapcsolódó cikkek
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">