Kleeneho hvězdička

Kleeneho hvězdička, Kleeneho operátor, Kleeneho uzávěr je unární operátor používaný v různých odvětvích matematické logiky a matematické informatiky, který lze aplikovat na symbol, část regulárního výrazu nebo na množinu symbolů či řetězců. V matematice se používá pro konstrukci volných monoidů. Aplikace Kleeneho operátoru na množinu V se zapisuje V^*. Nejčastěji se používá v regulárních výrazech, což je kontext, ve kterém tento operátor zavedl Stephen Cole Kleene pro charakterizaci určitých automatů, kde se používá ve významu „nula nebo více výskytů“ nebo (nepřesně) „nula nebo více opakování“.

Definice

V^* lze definovat takto:

1. Pokud V je množina řetězců, pak V^* je definováno jako nejmenší nadmnožina V, která obsahuje prázdný řetězec ε a je uzavřená vůči operaci zřetězení.
2. Pokud V je množina symbolů nebo znaků, pak V^* je množina všech řetězců nad V, včetně prázdného řetězce ε.

Množinu V^* můžeme také definovat jako množinu řetězců konečné délky, které lze generovat zřetězením libovolných prvků V, přičemž libovolný prvek může být použit opakovaně. Pokud V je buď prázdná množina ∅ nebo jednoprvková množina obsahující prázdný řetězec {ε}, pak V^* = {ε}; jestliže V je jiná konečná množina anebo spočetně nekonečná množina, pak V^* je spočetně nekonečná množina.

Kleeneho operátor se používá v přepisovacích pravidlech v zápisech či definicích generativních gramatik.

Odkazy

Související články

• Žolíkový znak

Reference

V tomto článku byl použit překlad textu z článku Kleene star na anglické Wikipedii.

Literatura

• HOPCROFT, John E.; ULLMAN, Jeffrey D. Introduction to Automata Theory, Languages, and Computation. 1. vyd. [s.l.]: Addison-Wesley, 1979. Dostupné online. ISBN 81-7808-347-7.