Estrella Kleene

En la teoría del lenguaje formal , la estrella de Kleene (o el operador de Kleene o el cierre de Kleene ) se refiere a dos operaciones unarias relacionadas , que pueden aplicarse tanto a un alfabeto de símbolos como a un lenguaje formal , un conjunto de cadenas (secuencias finitas de símbolos).

El operador estrella de Kleene sobre un alfabeto V genera el conjunto V* de todas las cadenas de longitud finita sobre V , ^{[ nota 1 ]} es decir, secuencias finitas cuyos elementos pertenecen a V ; en matemáticas, se conoce más comúnmente como la construcción de monoide libre . El operador estrella de Kleene sobre un lenguaje L genera otro lenguaje L* , el conjunto de todas las cadenas que se pueden obtener como una concatenación de cero o más elementos de L. En ambos casos, se permiten repeticiones.

Los operadores estrella de Kleene reciben su nombre del matemático estadounidense Stephen Cole Kleene , quien los introdujo por primera vez y los utilizó ampliamente para caracterizar autómatas para expresiones regulares .

Dado un alfabeto${\displaystyle V}$, definir

${\displaystyle V^{0}=\{\varepsilon \}}$(el conjunto 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{ y }}v\in V\}}$para cada${\displaystyle i>0,}$

dónde${\displaystyle wv}$denota la cadena obtenida al agregar el único carácter${\displaystyle v}$hasta el final de${\displaystyle w}$. Aquí,${\displaystyle V^{i}}$puede entenderse como el conjunto de todas las cadenas de longitud exactamente${\displaystyle i}$, con personajes de${\displaystyle V}$.

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

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

Dado un idioma${\displaystyle L}$(cualquier conjunto finito o infinito de cadenas), definir

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

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

y definir recursivamente el conjunto

${\displaystyle L^{i+1}=\{wv:w\in L^{i}{\text{ y }}v\in L\}}$para cada${\displaystyle i>0,}$

dónde${\displaystyle wv}$denota la cadena obtenida al concatenar${\displaystyle w}$y${\displaystyle v}$. Aquí,${\displaystyle L^{i}}$puede entenderse como el conjunto de todas las cadenas que se pueden obtener concatenando exactamente${\displaystyle i}$cadenas de${\displaystyle L}$, permitiendo repeticiones.

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

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

En algunos estudios formales de lenguaje (por ejemplo, la teoría AFL ) , se utiliza una variación de la operación estrella de Kleene llamada Kleene plus . El Kleene plus omite la${\displaystyle V^{0}}$o${\displaystyle L^{0}}$término en las uniones anteriores. En otras palabras, el Kleene más en${\displaystyle V}$es

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

o

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

Ejemplo de la estrella de Kleene aplicada a un conjunto de cadenas:

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

Ejemplo de la estrella de Kleene aplicada a un conjunto de cadenas sin la propiedad de prefijo :

{"a","ab","b"} ^* = { ε, "a", "ab", "b", "aa", "aab", "aba", "abab", "abb", "ba", "bab", "bb", ...}; En este ejemplo, la cadena "aab" se puede obtener de dos maneras diferentes. El algoritmo de Sardinas-Patterson se puede usar para comprobar, para un V dado , si algún miembro de V ^* se puede obtener de más de una manera.

Ejemplo de Kleene y Kleene plus aplicados a un conjunto de caracteres (siguiendo la convención del lenguaje de programación C, donde un carácter se denota con comillas simples y una cadena con comillas dobles):

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

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

• Si${\displaystyle V}$es cualquier conjunto finito o infinito numerable de caracteres, entonces${\displaystyle V^{*}}$es un conjunto infinitamente numerable. ^{[ 1 ]} Como resultado, cada lenguaje formal sobre un alfabeto finito o infinitamente numerable${\displaystyle \Sigma }$es numerable, ya que es un subconjunto del conjunto infinito numerable.${\displaystyle \Sigma ^{*}}$.
• ${\displaystyle (L^{*})^{*}=L^{*}}$, lo que significa que el operador estrella de Kleene es un operador unario idempotente , como${\displaystyle (L^{*})^{i}=L^{*}}$por cada${\displaystyle i\geq 1}$.
• ${\displaystyle V^{*}=\{\varepsilon \}}$, si${\displaystyle V}$es el conjunto vacío ∅. Para la versión del operador estrella de Kleene en lenguajes,${\displaystyle L^{*}=\{\varepsilon \}}$cuando${\displaystyle L}$es o bien el conjunto vacío ∅ o bien el conjunto unitario${\displaystyle \{\varepsilon \}}$.

Las cadenas forman un monoide con la concatenación como operación binaria y ε como elemento identidad. Además de las cadenas, la estrella de Kleene se define para cualquier monoide. 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 estrella completo . ^{[ 3 ]}

• Personaje comodín
• Glob (programación)

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