Kleene izar

Wikipedia, Entziklopedia askea
Jump to navigation Jump to search

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[aldatu | aldatu iturburu kodea]

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.

Adibideak[aldatu | aldatu iturburu kodea]

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[aldatu | aldatu iturburu kodea]

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