Kleene izar

Logika matematikoan eta konputazio-zientzietan, Kleene izar (Kleeneren klausura, Kleene-itxiera, Kleene star edo izar-itxiera ere deitua) karaktere-kate multzo baten gainean edo sinbolo-kate multzo (alfabeto) baten gainean aplikatzen den eragiketa unari bat da, eta kate multzo bat adierazten du, jatorrizko multzoetako kateetako hasierako taldeko edozein zenbaki hartzean osatu ahal duten taldea ordezkatzen du, errepikapenekin posibleki, eta kateatzean berekiko.

Klausuraren aplikazioak Kleeneren talde bat V-ri denotatzen dio V *. Oso erabilia da adierazpen erregularretan eta Stephen Kleenek (1909-1994) testuinguru honetan sartu zuen benetako automata baten ezaugarri izateko.

Definizioa eta notazioa

Multzo hau emanda

${\displaystyle V_{0}=\{\lambda \}\,}$

errekurtsiboki definitzen da:

${\displaystyle {\displaystyle V_{i+1}=\{wv:w\in V_{i}{\mbox{ and }}v\in V\}\,}\,}$ non ${\displaystyle i\geq 0\,.}$

${\displaystyle V}$ lengoaia formal bat bada, orduan ${\displaystyle V}$-ren ${\displaystyle i}$-garren berredura laburdura bat da ${\displaystyle V}$ bere buruarekin ${\displaystyle i}$ aldiz kateatuta adierazten duena. Hau da, ${\displaystyle V_{i}}$ ulertu ahal daiteke ${\displaystyle i}$ luzeradun karaktere-kate posible guztien multzoa dela, ${\displaystyle V}$-ko ikurrekin eratutakoak.

${\displaystyle V}$-ko Kleene-izarra honela definitzen da: ${\displaystyle V^{*}=\bigcup _{i\in \mathbb {N} }V_{i}=\left\{\lambda \right\}\cup V_{1}\cup V_{2}\cup V_{3}\cup \ldots .}$

Hau da, ${\displaystyle V}$ko ikurrekin eta luzera finiturekin osa daitezkeen kate posible guztien multzoa.

Adibideak

Kleeneren klausuraren adibidea karaktere bati aplikatua:

{"a"}* = {λ, "a", "aa", "aaa", "aaaa", "aaaaa", "aaaaaa",...}

Kleeneren klausuraren adibidea kate multzo bati aplikatua:

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

Kleeneren klausuraren adibidea karaktere multzo bati aplikatua:

{'a', 'b', 'c'}* = {λ, "a", "b", "c", "aa", "ab", "ac", "ba", "bb", "bc",...}

Erreferentziak

• John E. Hopcroft eta Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation. 3rd edition. Addison-Wesley Publishing Company, 2007. ISBN: 978-0321455369

Kanpo estekak

• Datuak: Q849775