Kleene stea

În logica matematică și informatică , steaua lui Kleene (sau închiderea lui Kleene sau operatorul lui Kleene ) este o operație unară definită pe un set de șiruri sau pe un set de simboluri sau caractere. În matematică, este cel mai bine cunoscut sub numele de construcția unui monoid liber . Aplicarea stelei lui Kleene la un set $V.$ ${\ displaystyle V}$ $V.$ este scris ca $V^{*}$ ${\ displaystyle V ^ {*}}$ $V ^ *$ ; este utilizat în mod normal în expresii regulate , contextul în care Stephen Kleene a introdus inițial acest concept, adică „zero sau mai mult”.

Noțiuni introductive

Este $LA$ ${\ displaystyle A}$ $LA$ un set pe care îl vom numi alfabet . Este definit ca universul lingvistic al $LA$ ${\ displaystyle A}$ $LA$ , și este indicat cu $A^{*}$ ${\ displaystyle A ^ {*}}$ $A ^ {*}$ , mulțimea formată din secvențele finite ale elementelor din $LA$ ${\ displaystyle A}$ $LA$ . Elementele $A^{*}$ ${\ displaystyle A ^ {*}}$ $A ^ {*}$ , numite și cuvinte , sunt obținute prin concatenarea unui număr arbitrar (dar finit) de elemente ale $LA$ ${\ displaystyle A}$ $LA$ , care poartă numele literelor alfabetului. De sine $\alpha$ ${\ displaystyle \ alpha}$ $\ alfa$ Și $\beta$ ${\ displaystyle \ beta}$ $\ beta$ sunt două cuvinte, indicăm cu $\alpha \beta$ ${\ displaystyle \ alpha \ beta}$ $\ alpha \ beta$ cuvântul obținut prin concatenarea cuvintelor date în ordinea în care apar.

Cuvântul gol , adică secvența constând din zero elemente ale $LA$ ${\ displaystyle A}$ $LA$ , este de obicei indicat cu simbolul $\varepsilon$ ${\ displaystyle \ varepsilon}$ $\ varepsilon$ . Următoarea proprietate se aplică cuvântului gol:

\alpha \varepsilon =\varepsilon \alpha =\alpha ,\quad \forall \alpha \in A^{*}.

{\ displaystyle \ alpha \ varepsilon = \ varepsilon \ alpha = \ alpha, \ quad \ forall \ alpha \ în A ^ {*}.}

{\ displaystyle \ alpha \ varepsilon = \ varepsilon \ alpha = \ alpha, \ quad \ forall \ alpha \ în A ^ {*}.}

Pentru fiecare element $X$ ${\ displaystyle x}$ $X$ din $LA$ ${\ displaystyle A}$ $LA$ , operația de concatenare este definită ca:

S_{x}\left(\alpha \right)=\alpha x,\quad \forall \alpha \in A^{*}.

{\ displaystyle S_ {x} \ left (\ alpha \ right) = \ alpha x, \ quad \ forall \ alpha \ în A ^ {*}.}

{\ displaystyle S_ {x} \ left (\ alpha \ right) = \ alpha x, \ quad \ forall \ alpha \ în A ^ {*}.}

Dovedește că $A^{*}$ ${\ displaystyle A ^ {*}}$ $A ^ {*}$ coincide cu închiderea inductivă a mulțimii formate de cuvântul gol $\varepsilon$ ${\ displaystyle \ varepsilon}$ $\ varepsilon$ în ceea ce privește setul de operații de concatenare definite pe toate elementele de $LA$ ${\ displaystyle A}$ $LA$ , sau:

A^{*}={\mathcal {C}}los\left(\left\{\varepsilon \right\},\left\{S_{x}\;|\;\forall x\in A\right\}\right).

{\ displaystyle A ^ {*} = {\ mathcal {C}} los \ left (\ left \ {\ varepsilon \ right \}, \ left \ {S_ {x} \; | \; \ forall x \ in A \ corect corect).}

{\ displaystyle A ^ {*} = {\ mathcal {C}} los \ left (\ left \ {\ varepsilon \ right \}, \ left \ {S_ {x} \; | \; \ forall x \ in A \ corect corect).}

Este limbajul definit pe alfabet $LA$ ${\ displaystyle A}$ $LA$ fiecare subset $L$ ${\ displaystyle L}$ $L$ din $A^{*}$ ${\ displaystyle A ^ {*}}$ $A ^ {*}$ . De sine $n\in N,a\in A$ ${\ displaystyle n \ in N, a \ in A}$ $n \ in N, a \ in A$ , este indicat cu $a^{n}$ ${\ displaystyle a ^ {n}}$ $a ^ {n}$ cuvântul de $A^{*}$ ${\ displaystyle A ^ {*}}$ $A ^ {*}$ obținută prin juxtapunere $n$ ${\ displaystyle n}$ $n$ ori $la$ ${\ displaystyle a}$ $la$ , sau:

a^{n}=\underbrace {aaa\ldots a} _{n}.

{\ displaystyle a ^ {n} = \ underbrace {aaa \ ldots a} _ {n}.}

{\ displaystyle a ^ {n} = \ underbrace {aaa \ ldots a} _ {n}.}

Dacă indicăm cu $L_{1}$ ${\ displaystyle L_ {1}}$ $L_ {1}$ Și $L_{2}$ ${\ displaystyle L_ {2}}$ $L_ {2}$ două limbi pe $LA$ ${\ displaystyle A}$ $LA$ , Putem defini următoarea operație de produs (sau concatenarea) între limbi: