Hvězda Kleene

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 5. prosince 2021; kontroly vyžadují 2 úpravy .

Kleene hvězda (nebo Kleene uzávěr ) v matematické logice a informatice je unární operace na souboru řetězců nebo charakterů . Kleeneův uzávěr sady V je označen V *. Široce se používá v regulárních výrazech .

Je-li V množina řetězců pak V * je minimální nadmnožina V , která obsahuje ε ( prázdný řetězec ) a je uzavřena zřetězením . Je to také množina všech řetězců získaných zřetězením nula nebo více řetězců z V . Jestliže V je množina symbolů pak V * je množina všech řetězců znaků z V s přidaným prázdným řetězcem.

Definice

Sada stupňů

$i$ Mocnina množiny je zřetězení množiny se sebou samými časy. $PROTI$ $PROTI$ $i-1$

Nulový stupeň libovolné množiny se nemění:

V^0 = \left\{\varepsilon \right\}

Zbývající stupně jsou definovány rekurzivně :

V^i = V^{i-1} V = \left\{wv \left|\, w \in V^{i-1} \land v \in V \right. \že jo\}

, kde .

i \v \N

If je sada znaků

PROTI

pak je sada řetězců znaků délky převzatých z .

V^i

i

PROTI

Star Kleene

Kleene uzávěr soupravy je $PROTI$

V^* = \bigcup_{i=0}^{\infty} V^i

To znamená, že se jedná o množinu všech řetězců konečné délky, generovaných prvky množiny . $PROTI$

Plus Kleene

Existuje operace podobná Kleene star- plus Kleene :

V^+ = \bigcup_{i=1}^{\infty} V^i

Jak vidíte, liší se tím, že v něm chybí prázdný řetězec. $V^0$

Vlastnosti

Komunikační operace:
1. $V^+ = V^*V$
2. $V^+ = V^* \Šipka doleva\varepsilon \in V$
Idempotence :

V^* = {V^*}^*

Uzávěr Kleene obsahuje generátorovou sadu:

V \subseteq V^*

Uzávěr Kleene vždy obsahuje prázdný řetězec:

\varepsilon \in V^*

Počítání :

\left|V^* \right| = \left|V^+ \right| = \alef_0 \Leftarrow \varnothing \ne V \ne \{\varepsilon\}

Příklady

Pro více řádků {"Go", "Russia"}* = {ε, "Go", "Rusko", "GoGo", "GoRussia", "RussiaGo", "RussiaRussia", "GoGoGo", "GoGoRussia", "GoRussiaGo", …}. Pro více postav {'a', 'b', 'c'}* = {ε, "a", "b", "c", "aa", "ab", "ac", "ba", "bb", "bc", "ca", "cb", "cc", "aaa", ...}. Pro sadu z prázdného řetězce

\left\{\varepsilon \right\}^* = \left\{\varepsilon \right\}^+ = \left\{\varepsilon \right\}

. Pro prázdnou sadu

\varnothing^* = \left\{\varepsilon \right\}

\varnothing^+ = \varnothing^* \varnothing = \varnothing

Generalizace

Řetězce tvoří monoid zřetězením s neutrálním prvkem . Kleeneovu definici hvězdy lze tedy rozšířit na jakýkoli monoid. $\varepsilon$

Viz také

Literatura

John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman. Úvod do teorie automatů, jazyků a počítání. - 3. vydání. - 2006. - 535 s. — ISBN 0321462254 .
Katrin Erk, Lutz Priese. Teoretická informatika: eine umfassende Einführung. — 2., ehm. - Springer-Verlag, 2002. - S. 27-29. — ISBN 3-540-42624-8 .