estrella kleene

Operación unaria en conjuntos de cadenas

En lógica matemática e informática , la estrella de Kleene (u operador de Kleene o cierre 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 monoide libre . La aplicación de la estrella Kleene a un conjunto se escribe como . Es muy utilizado 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 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 se puede describir como el conjunto que contiene la cadena vacía y todas las cadenas de longitud finita que se pueden generar 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 un conjunto contablemente infinito , entonces es un conjunto contablemente infinito. ^[1] Como consecuencia, cada lenguaje formal sobre un alfabeto finito o contablemente infinito es contable, ya que es un subconjunto del conjunto contablemente 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 , defina ${\displaystyle V}$

${\displaystyle V^{0}=\{\varepsilon \}}$(el idioma que consta únicamente de 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 . ${\displaystyle i>0}$

Si es un lenguaje formal, entonces , la -ésima potencia del conjunto es una abreviatura de la concatenación de tiempos de conjunto consigo mismo . Es decir, puede entenderse como el conjunto de todas las cadenas que se pueden representar 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 estrella 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 más

En algunos estudios formales del lenguaje (por ejemplo, la teoría AFL ), se utiliza una variación de la operación de la estrella de Kleene llamada Kleene plus . El Kleene plus omite el término en la unión anterior. En otras palabras, el 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 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 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 Kleene aplicada al conjunto vacío:

∅ ^* = {ε}.

Ejemplo de Kleene plus aplicado al set 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 uno , por tanto . ${\displaystyle V=\{\varepsilon \}}$ ${\displaystyle V^{i}=\{\varepsilon \}}$ ${\displaystyle i}$ ${\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 de Kleene se define para cualquier monoide, no sólo 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 ^* , 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 semirredondo estrella completo . ^[4]

Ver también

• Carácter comodín
• Globo (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 la Matemática Discreta . Brooks/Cole. pag. 656.ISBN​ 0534923739. La clausura de Kleene L ^* de L se define como . ${\textstyle \bigcup _{i=0}^{\infty }L^{i}}$
3. Esta ecuación se cumple porque cada elemento de V ⁺ debe estar compuesto de un elemento de V y un número finito de términos no vacíos en V o es solo un elemento de V (donde V mismo se recupera tomando V concatenado con ε).
4. Droste, M.; Kuich, W. (2009). "Capítulo 1: Serie Semirings y Poder Formal". Manual de autómatas ponderados . Monografías en Informática Teórica. Saltador. pag. 9. doi :10.1007/978-3-642-01492-5_1. ISBN 978-3-642-01491-8.

Otras lecturas

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