Kleene hvězda - Kleene star

V matematické logice a informatice , v Kleeneho hvězdy (nebo provozovatel Kleeneho nebo uzavření Kleeneho ) je unární operace , a to buď na sety z řetězců nebo na sady symbolů nebo znaků. V matematice je známější jako volná monoidová konstrukce. Aplikace hvězdy Kleene na sadu je napsána jako . Je široce používán pro regulární výrazy , což je kontext, ve kterém jej zavedl Stephen Kleene k charakterizaci určitých automatů , kde znamená „nulové nebo více opakování“. ${\ displaystyle V}$${\ displaystyle V^{*}}$

1. Pokud je množina řetězců, potom je definována jako nejmenší podmnožinou of který obsahuje prázdný řetězec a je uzavřen v rámci operace zřetězení řetězců .${\ displaystyle V}$${\ displaystyle V^{*}}$${\ displaystyle V}$ ${\ displaystyle \ varepsilon}$
2. Pokud je sada symbolů nebo znaků, pak je sada všech řetězců nad symboly v , včetně prázdného řetězce .${\ displaystyle V}$${\ displaystyle V^{*}}$${\ displaystyle V}$${\ displaystyle \ varepsilon}$

Sadu lze také popsat jako sadu obsahující prázdný řetězec a všechny řetězce konečné délky, které lze generovat zřetězením libovolných prvků , což umožňuje použití stejného prvku vícekrát. Pokud je buď prázdná množina ∅, nebo singletonová množina , pak ; pokud je nějaká jiná konečná množina nebo spočitatelně nekonečná množina , pak je spočitatelně nekonečná množina. V důsledku toho je každý formální jazyk přes konečnou nebo spočitatelně nekonečnou abecedu spočitatelný, protože je podmnožinou spočitatelně nekonečné množiny . ${\ displaystyle V^{*}}$${\ displaystyle V}$${\ displaystyle V}$${\ displaystyle \ {\ varepsilon \}}$${\ Displaystyle V^{*} = \ {\ varepsilon \}}$${\ displaystyle V}$${\ displaystyle V^{*}}$${\ displaystyle \ Sigma}$${\ displaystyle \ Sigma ^{*}}$

Operátory se používají v pravidlech přepisování pro generativní gramatiky .

Definice a zápis

Vzhledem k definici sady${\ displaystyle V}$

${\ Displaystyle V^{0} = \ {\ varepsilon \}}$ (jazyk sestávající pouze z prázdného řetězce),

${\ displaystyle V^{1} = V}$

a definujte rekurzivně sadu

${\ Displaystyle V^{i+1} = \ {wv: w \ in V^{i} {\ text {and}} v \ in V \}}$pro každého .${\ displaystyle i> 0}$

Pokud je formální jazyk, pak se tý výkon setu , je zkratka pro zřetězení setu se sebou samým krát. To znamená, že lze chápat jako soubor všech řetězců, které lze reprezentovat jako zřetězení řetězců v . ${\ displaystyle V}$${\ displaystyle V^{i}}$${\ displaystyle i}$${\ displaystyle V}$${\ displaystyle V}$${\ displaystyle i}$${\ displaystyle V^{i}}$${\ displaystyle i}$${\ displaystyle V}$

Definice Kleene hvězdy na je ${\ displaystyle V}$

${\ Displaystyle V^{*} = \ bigcup _ {i \ geq 0} V^{i} = V^{0} \ cup V^{1} \ cup V^{2} \ cup V^{3} \ cup V^{4} \ cup \ cdots.}$

To znamená, že hvězdný operátor Kleene je idempotentní unární operátor : pro každou sadu řetězců nebo znaků, jako pro všechny . ${\ displaystyle (V^{*})^{*} = V^{*}}$${\ displaystyle V}$${\ displaystyle (V^{*})^{i} = V^{*}}$${\ Displaystyle i \ geq 1}$

Kleene plus

V některých formálních jazykových studiích (např. Teorie AFL ) se používá variace na operaci hvězdy Kleene zvanou Kleene plus . Kleene plus tento termín ve výše uvedeném svazku vynechává . Jinými slovy, Kleene plus on je ${\ displaystyle V^{0}}$${\ displaystyle V}$

${\ Displaystyle V^{+} = \ bigcup _ {i \ geq 1} V^{i} = V^{1} \ cup V^{2} \ cup V^{3} \ cup \ cdots.}$

nebo

${\ displaystyle V^{+} = V^{*} V}$

Příklady

Příklad hvězdy Kleene aplikované na sadu řetězců:

{"ab", "c"} ^* = {ε, "ab", "c", "abab", "abc", "cab", "cc", "ababab", "ababc", "abcab", „abcc“, „cabab“, „cabc“, „ccab“, „ccc“, ...}.

Příklad Kleene plus aplikovaný na sadu znaků:

{"a", "b", "c"} ⁺ = {"a", "b", "c", "aa", "ab", "ac", "ba", "bb", "bc "," ca "," cb "," cc "," aaa "," aab ", ...}.

Kleene hvězda aplikovaná na stejnou znakovou sadu:

{"a", "b", "c"} ^* = {ε, "a", "b", "c", "aa", "ab", "ac", "ba", "bb", „bc“, „ca“, „cb“, „cc“, „aaa“, „aab“, ...}.

Příklad hvězdy Kleene aplikované na prázdnou sadu:

∅ ^* = {ε}.

Příklad použití Kleene plus na prázdnou sadu:

∅ ⁺ = ∅ ∅ ^* = {} = ∅,

kde zřetězení je asociativní a nekomutativní produkt.

Příklad Kleene plus a Kleene star aplikovaných na singletonovou sadu obsahující prázdný řetězec:

Pokud , pak také pro každého , tedy .${\ displaystyle V = \ {\ varepsilon \}}$${\ Displaystyle V^{i} = \ {\ varepsilon \}}$${\ displaystyle i}$${\ Displaystyle V^{*} = V^{+} = \ {\ varepsilon \}}$

Zobecnění

Řetězce tvoří monoid se zřetězením jako binární operací a ε prvkem identity. Kleeneova hvězda je definována pro jakýkoli monoid, nejen pro řetězce. Přesněji řečeno, nechť ( M , ⋅) být monoid a S ⊆ M . Pak S ^* je nejmenší submonoid M obsahující S ; to znamená, že S ^* obsahuje neutrální prvek M , množinu S , a je takový, že když x , y ∈ S ^* , pak x ⋅ y ∈ S ^* .

Kleeneova hvězda je navíc zobecněna zahrnutím operace *(a unie) do samotné algebraické struktury pojmem úplného hvězdného semiringu .

Viz také

• Zástupný znak
• Glob (programování)

Reference

Další čtení

• Hopcroft, John E .; Ullman, Jeffrey D. (1979). Úvod do teorie automatů, jazyků a výpočetní techniky (1. vydání). Addison-Wesley .