Estrella de kleene

Operación unaria sobre conjuntos de cuerdas

En lógica matemática y ciencias de la computación , la estrella de Kleene (u operador de Kleene o clausura de Kleene ) es una operación unaria , ya sea sobre conjuntos de cadenas o sobre conjuntos de símbolos o caracteres. En matemáticas, se conoce más comúnmente como construcción de monoide libre . La aplicación de la estrella de Kleene a un conjunto se escribe como . Se usa ampliamente para expresiones regulares , que es el contexto en el que fue introducido por Stephen Kleene para caracterizar ciertos autómatas , donde significa "cero o más repeticiones". ${\displaystyle V}$ ${\displaystyle V^{*}}$

1. Si es un conjunto de cadenas, entonces se define como el superconjunto más pequeño de que contiene la cadena vacía y se cierra bajo la operación de concatenación de cadenas . ${\displaystyle V}$ ${\displaystyle V^{*}}$ ${\displaystyle V}$ ${\displaystyle \varepsilon }$
2. Si es un conjunto de símbolos o caracteres, entonces es el conjunto de todas las cadenas sobre símbolos en , incluida la cadena vacía . ${\displaystyle V}$ ${\displaystyle V^{*}}$ ${\displaystyle V}$ ${\displaystyle \varepsilon }$

El conjunto también puede describirse como el conjunto que contiene la cadena vacía y todas las cadenas de longitud finita que pueden generarse concatenando elementos arbitrarios de , lo que permite el uso del mismo elemento varias veces. Si es el conjunto vacío ∅ o el conjunto singleton , entonces ; si es cualquier otro conjunto finito o conjunto numerablemente infinito , entonces es un conjunto numerablemente infinito. ^[1] En consecuencia, cada lenguaje formal sobre un alfabeto finito o numerablemente infinito es contable, ya que es un subconjunto del conjunto numerablemente infinito . ${\displaystyle V^{*}}$ ${\displaystyle V}$ ${\displaystyle V}$ ${\displaystyle \{\varepsilon \}}$ ${\displaystyle V^{*}=\{\varepsilon \}}$ ${\displaystyle V}$ ${\displaystyle V^{*}}$ ${\displaystyle \Sigma }$ ${\displaystyle \Sigma ^{*}}$

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

Definición y notación

Dado un conjunto , define ${\displaystyle V}$

${\displaystyle V^{0}=\{\varepsilon \}}$(el idioma que consiste únicamente en la cadena vacía),

${\displaystyle V^{1}=V}$,

y definir recursivamente el conjunto

${\displaystyle V^{i+1}=\{wv:w\in V^{i}{\text{ and }}v\in V\}}$para cada uno . ${\displaystyle i>0}$

Si es un lenguaje formal, entonces , la -ésima potencia del conjunto , es una forma abreviada de concatenar el conjunto consigo mismo por veces. Es decir, puede entenderse como el conjunto de todas las cadenas que pueden representarse como la concatenación de cadenas en . ${\displaystyle V}$ ${\displaystyle V^{i}}$ ${\displaystyle i}$ ${\displaystyle V}$ ${\displaystyle V}$ ${\displaystyle i}$ ${\displaystyle V^{i}}$ ${\displaystyle i}$ ${\displaystyle V}$

La definición de la estrella de Kleene es ^[2] ${\displaystyle V}$

${\displaystyle V^{*}=\bigcup _{i\geq 0}V^{i}=V^{0}\cup V^{1}\cup V^{2}\cup V^{3}\cup V^{4}\cup \cdots .}$

Esto significa que el operador estrella de Kleene es un operador unario idempotente : para cualquier conjunto de cadenas o caracteres, como para cada . ${\displaystyle (V^{*})^{*}=V^{*}}$ ${\displaystyle V}$ ${\displaystyle (V^{*})^{i}=V^{*}}$ ${\displaystyle i\geq 1}$

Kleene plus

En algunos estudios formales del lenguaje (por ejemplo, la teoría AFL ) se utiliza una variación de la operación de estrella de Kleene llamada Kleene plus . La operación Kleene plus omite el término en la unión anterior. En otras palabras, la operación Kleene plus on es ${\displaystyle V^{0}}$ ${\displaystyle V}$

${\displaystyle V^{+}=\bigcup _{i\geq 1}V^{i}=V^{1}\cup V^{2}\cup V^{3}\cup \cdots ,}$

o

${\displaystyle V^{+}=V^{*}V.}$^[3]

Ejemplos

Ejemplo de estrella de 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", "bb", "bc", "ca", "cb", "cc", "aaa", "aab", ...}.

Estrella de Kleene aplicada al mismo conjunto de caracteres:

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

Ejemplo de estrella de Kleene aplicada al conjunto vacío:

∅ ^* = {ε}.

Ejemplo de Kleene plus aplicado al conjunto vacío:

∅ ⁺ = ∅ ∅ ^* = { } = ∅,

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 , entonces también para cada , por lo tanto . ${\displaystyle V=\{\varepsilon \}}$ ${\displaystyle V^{i}=\{\varepsilon \}}$ ${\displaystyle i}$ ${\displaystyle V^{*}=V^{+}=\{\varepsilon \}}$

Generalización

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

Además, la estrella de Kleene se generaliza al incluir la operación * (y la unión) en la propia estructura algebraica mediante la noción de semianillo estelar completo . ^[4]

Véase también

• Carácter comodín
• Glob (programación)

Referencias

1. Nayuki Minase (10 de mayo de 2011). "Conjuntos contables y estrella Kleene". Proyecto Nayuki . Consultado el 11 de enero de 2012 .
2. Fletcher, Peter; Hoyle, Hughes; Patty, C. Wayne (1991). Fundamentos de las matemáticas discretas . Brooks/Cole. pág. 656. ISBN 0534923739El cierre de Kleene L * ^de L se define como . ${\textstyle \bigcup _{i=0}^{\infty }L^{i}}$
3. Esta ecuación es válida porque cada elemento de V ⁺ debe estar compuesto por un elemento de V y un número finito de términos no vacíos en V o es simplemente un elemento de V (donde V mismo se recupera tomando V concatenado con ε).
4. Droste, M.; Kuich, W. (2009). "Capítulo 1: Semirings and Formal Power Series". Manual de autómatas ponderados . Monografías en informática teórica. Springer. pág. 9. doi :10.1007/978-3-642-01492-5_1. ISBN . 978-3-642-01491-8.

Lectura adicional

• Hopcroft, John E. ; Ullman, Jeffrey D. (1979). Introducción a la teoría de autómatas, lenguajes y computación (1.ª ed.). Addison-Wesley .