Tähti Kleene

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 5. joulukuuta 2021 tarkistetusta versiosta . tarkastukset vaativat 2 muokkausta .

Kleene-tähti (tai Kleenen sulkeminen ) matemaattisessa logiikassa ja tietojenkäsittelytieteessä on unaarinen operaatio merkkijono- tai merkkijoukolle . Joukon V Kleene-sulkeminen on merkitty V *:lla. Käytetään laajasti säännöllisissä lausekkeissa .

Jos V on merkkijonojoukko silloin V * on V:n minimisuperjoukko , joka sisältää ε:n ( tyhjän merkkijonon ) ja on suljettu ketjutuksessa . Se on myös kaikkien merkkijonojen joukko, joka on saatu ketjuttamalla nolla tai useampi merkkijono V :stä . Jos V on joukko symboleja silloin V * on kaikkien V :n merkkijonojen joukko, joihin on lisätty tyhjä merkkijono.

Määritelmä

Tutkintosarja

$i$ Joukon th potenssi on joukon ketjutus itsensä kanssa . $V$ $V$ $i-1$

Minkä tahansa joukon nolla-aste on muuttumaton:

V^0 = \vasen\{\varepsilon \oikea\}

Loput asteet määritellään rekursiivisesti :

V^i = V^{i-1} V = \vasen\{wv \vasen|\, w \in V^{i-1} \land v \in V \oikea. \oikea\}

, missä .

i \in \N

If on joukko merkkejä

V

sitten on joukko pituisia merkkijonoja, jotka on otettu .

V^i

i

V

Star Kleene

Sarjan Kleene-suljin on $V$

V^* = \bigcup_{i=0}^{\infty} V^i

Toisin sanoen tämä on kaikkien äärellisen pituisten merkkijonojen joukko, jotka on generoitu joukon elementeillä . $V$

Plus Kleene

On olemassa samanlainen toimenpide kuin Kleene star - plus Kleene :

V^+ = \bigcup_{i=1}^{\infty} V^i

Kuten näet, se eroaa siinä, että se puuttuu sisältäen tyhjän merkkijonon. $V^0$

Ominaisuudet

Viestintätoiminnot:
1. $V^+ = V^*V$
2. $V^+ = V^* \nuoli vasen oikealle \varepsilon \in V$
Idempotenssi :

V^* = {V^*}^*

Kleene-suljin sisältää generaattorisarjan:

V \subseteq V^*

Kleene-sulkeminen sisältää aina tyhjän merkkijonon:

\varepsilon \in V^*

Laskeminen :

\left|V^* \oikea| = \left|V^+ \right| = \alef_0 \Leftarrow \varnothing \ne V \ne \{\varepsilon\}

Esimerkkejä

Useille riveille {"Go", "Russia"}* = {ε, "Go", "Russia", "GoGo", "GoRussia", "RussiaGo", "RussiaRussia", "GoGoGo", "GoGoRussia", "GoRussiaGo", …}. Useille hahmoille {'a', 'b', 'c'}* = {ε, "a", "b", "c", "aa", "ab", "ac", "ba", "bb", "bc", "ca", "cb", "cc", "aaa", ...}. Joukkoon tyhjästä merkkijonosta

\left\{\varepsilon \right\}^* = \left\{\varepsilon \right\}^+ = \left\{\varepsilon \right\}

. Tyhjälle sarjalle

\varnothing^* = \vasen\{\varepsilon \oikea\}

\varnothing^+ = \varnothing^* \varnothing = \varnothing

Yleistys

Jouset muodostavat monoidin ketjuttamalla neutraalin elementin . Siten Kleenen tähden määritelmä voidaan laajentaa mihin tahansa monoidiin. $\varepsilon$

Katso myös

Kirjallisuus

John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman. Johdatus automaatioteoriaan, kieliin ja laskemiseen. - 3. painos. - 2006. - 535 s. — ISBN 0321462254 .
Katrin Erk, Lutz Priese. Teoreettinen tieto: eine umfassende Einführung. - 2., erw. - Springer-Verlag, 2002. - S. 27-29. — ISBN 3-540-42624-8 .