En lógica matemática e informática , la estrella de Kleene (o el operador de Kleene o el cierre de Kleene ) es una operación unaria , ya sea en conjuntos de cadenas o en 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 de Kleene a un decorado está escrito 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".
- Si es un conjunto de cadenas, entonces se define como el superconjunto más pequeño deque contiene la cadena vacía y se cierra bajo la operación de concatenación de cadenas .
- 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 .
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 , permitiendo el uso del mismo elemento varias veces. Sies el conjunto vacío ∅ o el conjunto singleton, luego ; Sies cualquier otro conjunto finito o conjunto infinito numerable , entonceses un conjunto infinito contable. [1] Como consecuencia, cada lenguaje formal sobre un alfabeto finito o infinito numerable es contable, ya que es un subconjunto del conjunto infinito numerable .
Los operadores se utilizan para reescribir reglas para gramáticas generativas .
Definición y notación
Dado un conjunto definir
- (el idioma que consiste solo en la cadena vacía),
y definir recursivamente el conjunto
- para cada .
Si es un lenguaje formal, entonces , la -ésimo poder del conjunto , es una abreviatura de la concatenación de un conjunto consigo mismo veces. Es decir,puede entenderse como el conjunto de todas las cadenas que se pueden representar como la concatenación de cadenas en .
La definición de la estrella de Kleene en es [2]
Esto significa que el operador estrella de Kleene es un operador unario idempotente : para cualquier conjunto de cadenas o caracteres, como para cada .
Kleene plus
En algunos estudios formales del lenguaje (por ejemplo, la teoría AFL ) se utiliza una variación de la operación estelar de Kleene llamada Kleene plus . El Kleene plus omite eltérmino en la unión anterior. En otras palabras, el Kleene plus en es
o
Ejemplos de
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 , Después también para cada , por eso .
Generalización
Las cadenas forman un monoide con la concatenación como operación binaria y ε el elemento de identidad. La estrella de Kleene se define para cualquier monoide, no solo para cuerdas. Más precisamente, sea ( M , ⋅) es 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 estructura algebraica misma mediante la noción de semirrígido estelar completo . [4]
Ver también
Referencias
- ^ Nayuki Minase (10 de mayo de 2011). "Conjuntos contables y estrella de Kleene" . Proyecto Nayuki . Consultado el 11 de enero de 2012 .
- ^ Ebbinghaus, Heinz-Dieter ; Flum, Jörg; Thomas, Wolfgang (1994). Lógica matemática (2ª ed.). Nueva York : Springer . pag. 656. ISBN 0-387-94258-0.
El cierre de Kleene L * de L se define como.
- ^ La ecuación correcta 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 en sí se recupera tomando V concatenado con ε).
- ^ Droste, M .; Kuich, W. (2009). "Capítulo 1: Semirings y series de 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 .