Estrella kleene

En la lógica matemática y la ciencia informática, Kleene star (o Kleene operator o Cierre de Kleene) es una operación sin sentido, ya sea en conjuntos de cuerdas o en conjuntos de símbolos o caracteres. En matemáticas, es más comúnmente conocido como la construcción monoide gratuita. La aplicación de la estrella Kleene a un conjunto V{displaystyle V} está escrito como VAlternativa Alternativa {displaystyle V^{*}. Es ampliamente utilizado para expresiones regulares, que es el contexto en el que fue introducido por Stephen Kleene para caracterizar ciertas automatas, donde significa "cero o más repeticiones".

1. Si V{displaystyle V} es un conjunto de cuerdas, entonces VAlternativa Alternativa {displaystyle V^{*} se define como el superset más pequeño de V{displaystyle V} que contiene la cuerda vacía ε ε {displaystyle varepsilon } y está cerrado bajo la operación de concatenación de cadenas.
2. Si V{displaystyle V} es un conjunto de símbolos o caracteres, entonces VAlternativa Alternativa {displaystyle V^{*} es el conjunto de todas las cadenas sobre símbolos en V{displaystyle V}, incluyendo la cuerda vacía ε ε {displaystyle varepsilon }.

El set VAlternativa Alternativa {displaystyle V^{*} también se puede describir como el conjunto que contiene la cadena vacía y todas las cadenas de longitud finita que pueden ser generadas por elementos arbitrarios concatenantes de V{displaystyle V}, permitiendo el uso del mismo elemento varias veces. Si V{displaystyle V} es el conjunto vacío ∅ o el conjunto de un solotón {}ε ε }{displaystyle {varepsilon}}, entonces VAlternativa Alternativa ={}ε ε }{displaystyle V^{*}={varepsilon {}}; si V{displaystyle V} es cualquier otro conjunto finito o conjunto contablemente infinito, entonces VAlternativa Alternativa {displaystyle V^{*} es un conjunto contablemente infinito. Como consecuencia, cada idioma formal sobre un alfabeto finito o contablemente infinito .. {displaystyle Sigma } es contable, ya que es un subconjunto del conjunto contablemente infinito .. Alternativa Alternativa {displaystyle Sigma ^{*}.

Los operadores se utilizan en reglas de reescritura para gramáticas generativas.

Definición y notación

Dado un conjunto V{displaystyle V}definir

V0={}ε ε }{displaystyle V^{0}={varepsilon {}} (el lenguaje que consiste sólo en la cuerda vacía),

V1=V{displaystyle V^{1}=V}

y definir recursivamente el conjunto

Vi+1={}wv:w▪ ▪ Viyv▪ ▪ V}{displaystyle V^{i+1}={wv:win V. para cada uno 0}" xmlns="http://www.w3.org/1998/Math/MathML">i■0{displaystyle i confía0}0" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1f49f2878fd68a89c3da37eb537198e887cf0293" style="vertical-align: -0.338ex; width:5.063ex; height:2.176ex;"/>.

Si V{displaystyle V} es un lenguaje formal, entonces Vi{displaystyle V^{i}, el i{displaystyle i}-el poder del conjunto V{displaystyle V}, es un cortocircuito para la concatenación de conjunto V{displaystyle V} con sí mismo i{displaystyle i} veces. Eso es, Vi{displaystyle V^{i} se puede entender que es el conjunto de todas las cuerdas que pueden ser representadas como la concatenación de i{displaystyle i} cuerdas en V{displaystyle V}.

La definición de estrella kleene en V{displaystyle V} es

VAlternativa Alternativa =⋃ ⋃ i≥ ≥ 0Vi=V0∪ ∪ V1∪ ∪ V2∪ ∪ V3∪ ∪ V4∪ ∪ ⋯ ⋯ .{displaystyle V^{*}=bigcup _{igeq - ¿Qué? V^{1}cup V^{2}cup V^{3}cup V^{4}cup cdots.}

Esto significa que el operador estrella Kleene es un operador indefinido: ()VAlternativa Alternativa )Alternativa Alternativa =VAlternativa Alternativa {displaystyle (V^{*}=V^{*} para cualquier conjunto V{displaystyle V} de cuerdas o caracteres, como ()VAlternativa Alternativa )i=VAlternativa Alternativa {displaystyle (V^{*}=V^{*} para todos i≥ ≥ 1{displaystyle igeq 1}.

Kleene plus

En algunos estudios de lenguaje formal, (por ejemplo, la teoría de la AFL) una variación en la operación estrella de Kleene llamada la Kleene plus se utiliza. El Kleene más omite el V0{displaystyle V^{0} término en la unión anterior. En otras palabras, el Kleene más encendido V{displaystyle V} es

V+=⋃ ⋃ i≥ ≥ 1Vi=V1∪ ∪ V2∪ ∪ V3∪ ∪ ⋯ ⋯ .{displaystyle V^{+}=bigcup _{igeq 1}V^{i}=V^{1}cup V^{2}cup V^{3}cup cdots.}

o

V+=VAlternativa Alternativa V{displaystyle V^{+}=V^{*}V}

Ejemplos

Ejemplo de estrella Kleene aplicada a un conjunto de cuerdas:

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

Ejemplo de Kleene plus aplicado a un conjunto de caracteres:

A, "b", "c"⁺ = "a", "b", "c", "aa", "ab", "ac", "ba", "bc", "ca", "cb", "cc", "aaaaa", "aab",...}.

Estrella de Kleene aplicada al mismo conjunto de caracteres:

A, "b", "c"^* = { ε, "a", "b", "c", "aa", "ab", "ac", "ba", "bc", "ca", "cb", "cc", "aaaa", "aab",...}.

Ejemplo de estrella Kleene aplicada al conjunto vacío:

∅^* = {ε}.

Ejemplo de Kleene plus aplicado al conjunto vacío:

∅⁺ Descubrimiento^* = { } = ∅,

donde la concatenación es un producto asociativo y no conmutativo.

Ejemplo de Kleene plus y Kleene star aplicados al conjunto singleton que contiene la cadena vacía:

Si V={}ε ε }{displaystyle V={varepsilon {}}, entonces también Vi={}ε ε }{displaystyle V^{i}={varepsilon {}} para cada uno i{displaystyle i}, por lo tanto VAlternativa Alternativa =V+={}ε ε }{displaystyle V^{*}=V^{+}={varepsilon {}}.

Generalización

Las cadenas forman un monoide con concatenación como operación binaria y ε como elemento de identidad. La estrella Kleene se define para cualquier monoide, no solo para cuerdas. Más precisamente, sea (M, ⋅) un monoide, y S ⊆ M. Entonces S^* es el submonoide más pequeño de M que contiene S; es decir, S^* contiene el elemento neutro de M, el conjunto S, y es tal que si x,y ∈ S^*, luego x⋅y ∈ S^*.

Además, la estrella de Kleene se generaliza al incluir la operación * (y la unión) en la estructura algebraica misma mediante la noción de estrella semianular completa.