Hvězda Kleene

Kleene hvězda , někdy nazývaný zavírání Kleene nebo iterativní uzávěr je v teorii jazyka , operátor unární používané při popisu formálních jazyků . Jméno hvězdy pochází z použité notace, hvězdička , a Kleene od Stephena Colea Kleena, který ji představil.

Kleeneova hvězda je jedním ze tří základních operátorů používaných k definování regulárního výrazu , spolu se zřetězením a množinovým spojením .

Při použití na sadu je výsledkem jazyk definovaný jako: $X$ $X ^ {*}$

Pokud je abeceda , to znamená, že sada symbolů nebo znaků, pak je množina slov nad , prázdné slovo hotelu. $X$ $X ^ {*}$ $X$ $\ varepsilon$
Pokud je jazyk , pak je nejmenší jazyk, který jej obsahuje, který obsahuje a který je stabilní zřetězením . $X$ $X ^ {*}$ $\ varepsilon$

Příklady

Pro abecedu máme $\ {ABC \}$

\ {a, b, c \} ^ {*} = \ {\ varepsilon, a, b, c, aa, ab, ac, ba, bb, bc, ca, cb, cc, aaa, \ ldots \}

Pro část složenou ze dvou slov a na abecedu získáme $X = \ {aa, b \}$ $aa$ $b$ $\ {a, b \}$

\ {aa, b \} ^ {*} = \ {\ varepsilon, b, aa, bb, aab, baa, bbb, aaaa, aabb, baab, bbaa, bbbb, \ ldots \}

Definice

Říkáme Kleenova hvězdou součást standardu A monoid na submonoid vygenerovaný pomocí . Tento submonoid je známý . Jako obvykle pro operace uzavření lze definovat třemi ekvivalentními způsoby: $X$ $M$ $X$ $X ^ {*}$

$X ^ {*}$ je nejmenší část kontejneru a neutrální prvek a uzavřený pro provoz . $M$ $X$ $M$ $M$
$X ^ {*}$ je průsečík všech obsahujících submonoidů . $M$ $X$
$X ^ {*}$ je sada všech produktů formuláře , pro a . $x_ {1} x_ {2} \ cdots x_ {n}$ $n \ geq 0$ $x_ {1}, x_ {2}, \ ldots, x_ {n} \ v X$

Pokud jde o generátorovou soustavu monoidu , máme zejména . $X$ $M$ $X ^ {*} = M$

Případ volného monoidu

V případě abecedy označíme množinu všech slov . Sada je monoidem pro zřetězení a je generována (aby byla docela přísná, je generována slovy složenými z písmene, které identifikujeme s písmeny). $NA$ $A ^ {*}$ $NA$ $A ^ {*}$ $NA$ $A ^ {*}$

Pokud je součástí , pak je submonoid, jehož může nebo nemusí být volný. Je zvykem zaznamenávat to jako celek $X$ $A ^ {*}$ $X ^ {*}$ $A ^ {*}$ $X ^ {n}$

X ^ {n} = \ {x_ {1} x_ {2} \ cdots x_ {n} \ mid x_ {1}, x_ {2}, \ ldots, x_ {n} \ v X \}

všech položek výrobků . Pak máme vzorec $ne$ $X$

X ^ {*} = \ bigcup _ {{n \ geq 0}} X ^ {n}

Pokud je volně generované submonoid , že je-li každé slovo se vyrábí v jedinečné cestě od slova , říkáme, že je kodex nebo který je základem of . $X ^ {*}$ $X$ $X ^ {*}$ $X$ $X$ $X$ $X ^ {*}$

Například sada je kód a sada není kód, protože slovo má obě faktorizace $X = \ {aa, b \}$ $X = \ {a, ab, ba \}$ $aba$

aba = ab . a = a . ba .

Provozovatel plus

Operátor navíc , také volal správné hvězda nebo pozitivní hvězda , je operátor analogický Kleenova hvězdy. Sdružuje s částí jednoho půl skupiny dílčí poloviny skupina generované pomocí , známý . My máme $X$ $M$ $X$ $X ^ {+}$

X ^ {+} = \ bigcup _ {{n> 0}} X ^ {n}

Jako obvykle u hvězdy lze operátor plus definovat třemi ekvivalentními způsoby:

$X ^ {+}$ je nejmenší část kontejneru a uzavřena pro provoz . $M$ $X$ $M$
$X ^ {+}$ je průsečík všech obsahujících podskupin . $M$ $X$
$X ^ {+}$ je sada všech produktů formuláře , pro a . $x_ {1} x_ {2} \ cdots x_ {n}$ $n> 0$ $x_ {1}, x_ {2}, \ ldots, x_ {n} \ v X$

V monoidu máme následující vztahy mezi hvězdou a plusovým operátorem:

{\ displaystyle X ^ {*} = X ^ {+} \ pohár \ {\ varepsilon \}, \ X ^ {+} = XX ^ {*} = X ^ {*} X.}

Vztahy mezi hvězdou a kladnou hvězdou byly předmětem mnoha prezentací; jedním z nejúplnějších je Brzozowski , Grant a Shallit

Opakování a doplňování hvězd

Dvě operace na formálních jazycích, které jsou hvězdou (pozitivní nebo ne) a přechodem na doplněk, mají pozoruhodné algebraické vlastnosti: první je idempotentní, protože pro jakýkoli jazyk a druhá je involutivní, protože ve skutečnosti doplněk doplňku jazyk je výchozím jazykem. ${\ displaystyle (L ^ {*}) ^ {*} = L ^ {*}}$ $L$

Opakování těchto dvou operací z daného jazyka nevytváří nekonečno jazyků, ale konečné číslo. Tento jev, který pozoroval David Peleg v roce 1984, je třeba dát do souvislosti s již starým topologickým výsledkem Kuratowského , uzavírací / doplňkové věty Kuratowského . $L$

Abychom toto tvrzení dokázali, uvažujeme tedy o těchto dvou operacích

{\ displaystyle L \ mapsto L ^ {*}}

{\ displaystyle L \ mapsto L ^ {-}}

hvězda a doplňování. Tyto operace jsou zapsány v postfixované notaci. Máme zejména

{\ displaystyle L ^ {**} = L ^ {*}}

(idempotence) a (involuce).

{\ displaystyle L ^ {-} = L}

Řadu operací lze proto vždy zjednodušit nahrazením postupných stejných operací a jsme přivedeni zpět ke střídání hvězd a doplňků. Tvrzení vychází z identity

{\ displaystyle L ^ {* - * - * - *} = L ^ {* - *}}

který říká, že posloupnost 8 operací může být nahrazena posloupností pouze 4 operací (s přihlédnutím ke skutečnosti, že posloupnost může začínat nebo končit doplňováním).

Demonstrace

Abychom tento vzorec dokázali, nejprve ukážeme zařazení

{\ displaystyle L ^ {* - * - *} \ subseteq L ^ {*} \ qquad (1)}

Toto zahrnutí je získáno od

{\ displaystyle L ^ {* -} \ subseteq L ^ {* - *}}

poté přejde na doplňkové:

{\ displaystyle L ^ {* -} = L ^ {*} \ supseteq L ^ {* - * -}}

a nakonec aplikací hvězdy

{\ displaystyle L ^ {**} = L ^ {*} \ supseteq L ^ {* - * - *}}

Rovnice (1) dává aplikací doplňku a potom hvězdy:

{\ displaystyle L ^ {* - * - * - *} \ supseteq L ^ {* - *}}

Na druhé straně, substitucí pro v rovnici (1), dostaneme: ${\ displaystyle L ^ {* -}}$ $L$

{\ displaystyle L ^ {* - * - * - *} \ subseteq L ^ {* - *}}

Dvě nerovnosti dávají požadovaný výsledek.

Rozšíření uvádí článek, který již citovali Brzozowski, Grant a Shallit.

Případ racionálních jazyků

Tyto pravidelné jazyky nebo pravidelný jsou popsané regulárními výrazy , které je Kleene hvězda podílejí zásadním způsobem: je to ona, kdo prošel kolem nekonečné jazyky. Odpovídající konstrukce na deterministických konečných automatech prochází mezikrokem pomocí nedeterministického konečného automatu . V případě, že minimální automat rozpoznávat jazyk má prohlášení o minimální deterministický konečný automat rozpoznávající plechovku, v zásadě států. Nyní je již dlouho známo, že tento počet stavů je nanejvýš , a přesněji nanejvýš , kde je počet terminálních stavů, které nejsou počátečním stavem. Je možná celá sada mezilehlých hodnot. $L$ $ne$ ${\ displaystyle L ^ {*}}$ $2 ^ {n}$ ${\ displaystyle 3/4 \ cdot 2 ^ {n}}$ ${\ displaystyle 2 ^ {n-1} + 2 ^ {n-1-k}}$ $k$

Jedno slovo hvězda

Rodina formálních jazyků získaných z jazyků, které jsou hvězdou slova, booleovskými závěrečnými operacemi, je poměrně omezená rodina. Připouští účinnou rovníkovou charakteristiku, která umožňuje rozhodnout, zda daný jazyk patří do této rodiny.

Poznámky a odkazy

Janusz Brzozowski , Elyot Grant a Jeffrey Shallit , „ Uzávěry ve formálních jazycích a Kuratowského věta “, International Journal of Foundations of Computer Science , sv. 22, n o 02,2011, str. 301–321 ( ISSN 0129-0541 , DOI 10.1142 / S0129054111008052 , arXiv 0901.3761 )
David Peleg , „ Zobecněný fenomén uzavírání a doplňování, “ Diskrétní matematika , sv. 50,1984, str. 285-293 ( ISSN 0012-365X , DOI 10.1016 / 0012-365X (84) 90055-4 , číst online ).
Peleg 1984 , Lemma 3.1.
Matúš Palmovský, „ Kleeneho uzavření a složitost stavu “, RAIRO-Theor. Inf. Appl. , sv. 50,2016, str. 251–261 ( DOI 10.1051 / ita / 2016024 ).
Laure Daviaud a Charles Paperman , „ Třídy jazyků generovaných hvězdou Kleene slova “, Information and Computation , sv. 262,2018, str. 90–109 ( ISSN 0890-5401 , DOI 10.1016 / j.ic.2018.07.002 ).

Bibliografie

(en) Stephen C. Kleene , „Zastoupení událostí v nervových sítích a konečných automatech“ , Claude E. Shannon a John McCarthy (eds), Automata Studies , Princeton, Princeton University Press, kol. "Annals matematiky studií" ( n O 34),1956, viii + 285 s. ( ISBN 978-0691079165 ) , str. 3-41
Jacky Akoka a Isabelle Comyn-Wattiau (redakce), Encyclopedia of Computing and Information Systems , Paříž, Vuibert ,2006, xxxv + 1941 s. ( ISBN 978-2-7117-4846-4 )
Olivier Carton, Formální jazyky, vyčíslitelnost a složitost: bakalářský a magisterský titul z matematiky nebo informatiky, výpočetní technika možnost agregace matematiky , Paříž, Vuibert ,2008, 237 s. ( ISBN 978-2-7117-2077-4 , online prezentace )
Jacques Sakarovitch , Elements of automata theory , Vuibert ,2003, 816 s. ( ISBN 978-2-7117-4807-5 )

Podívejte se také