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 notazioaAldatu

Multzo hau emanda

 

errekurtsiboki definitzen da:

  non  

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

 -ko Kleene-izarra honela definitzen da:  

Hau da,  ko ikurrekin eta luzera finiturekin osa daitezkeen kate posible guztien multzoa.

AdibideakAldatu

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",...}

ErreferentziakAldatu

  • 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 estekakAldatu