Estrella Kleene

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 5 de diciembre de 2021; las comprobaciones requieren 2 ediciones .

La estrella de Kleene (o el cierre de Kleene ) en lógica matemática e informática es una operación unaria en un conjunto de cadenas o caracteres . El cierre de Kleene de un conjunto V se denota por V *. Ampliamente utilizado en expresiones regulares .

Si V es un conjunto de cadenas entonces V * es el superconjunto mínimo de V que contiene ε ( la cadena vacía ) y se cierra bajo concatenación . También es el conjunto de todas las cadenas obtenidas al concatenar cero o más cadenas de V . Si V es un conjunto de símbolos entonces V * es el conjunto de todas las cadenas de caracteres de V con una cadena vacía añadida.

Definición

Conjunto de grados

$i$ La potencia th de un conjunto es la concatenación de un conjunto consigo mismo veces. $V$ $V$ $i-1$

El grado cero de cualquier conjunto no cambia:

V^0 = \izquierda\{\varepsilon \derecha\}

Los grados restantes se definen recursivamente :

V^i = V^{i-1} V = \left\{wv \left|\, w \in V^{i-1} \land v \in V \right. \Correcto\}

, donde .

yo \en \N

Si es un conjunto de caracteres

V

entonces es el conjunto de cadenas de caracteres de longitud tomado de .

yo

i

V

Estrella Kleene

El cierre Kleene del conjunto es $V$

V^* = \bigcup_{i=0}^{\infty} V^i

Es decir, este es el conjunto de todas las cadenas de longitud finita, generado por los elementos del conjunto . $V$

Más Kleene

Hay una operación similar a la estrella Kleene - más Kleene :

V^+ = \bigcup_{i=1}^{\infty} V^i

Como puede ver, se diferencia en que no contiene una cadena vacía. $V^0$

Propiedades

Operaciones de comunicación:
1. $V^+ = V^*V$
2. $V^+ = V^* \Leftrightarrow \varepsilon \in V$
Idempotencia :

V^* = {V^*}^*

El cierre Kleene incluye el grupo electrógeno:

V \subseteq V^*

El cierre de Kleene siempre contiene la cadena vacía:

\varepsilon \in V^*

contando :

\izquierda|V^* \derecha| = \izquierda|V^+ \derecha| = \alef_0 \Leftarrow \varnada \ne V \ne \{\varepsilon\}

Ejemplos

Para varias filas {"Ir", "Rusia"}* = {ε, "Ir", "Rusia", "IrIr", "IrRusia", "RusiaIr", "RusiaRusia", "IrIrGo", "IrIrRusia", "IrRusiaIr", …}. Para varios personajes {'a', 'b', 'c'}* = {ε, "a", "b", "c", "aa", "ab", "ac", "ba", "bb", "bc", "ca", "cb", "cc", "aaa", ...}. Para un conjunto de una cadena vacía

\left\{\varepsilon \right\}^* = \left\{\varepsilon \right\}^+ = \left\{\varepsilon \right\}

. Por un conjunto vacío

\varnada^* = \izquierda\{\varepsilon \derecha\}

\varnada^+ = \varnada^* \varnada = \varnada

Generalización

Las cadenas forman un monoide por concatenación con un elemento neutro . Por lo tanto, la definición de estrella de Kleene se puede extender a cualquier monoide. $\varepsilon$

Véase también

Literatura

John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman. Introducción a la teoría de autómatas, lenguajes y computación. - 3ra edición. - 2006. - 535 págs. — ISBN 0321462254 .
Katrin Erk, Lutz Priese. Theoretische Informatik: eine umfassende Einführung. - 2., eh. - Springer-Verlag, 2002. - S. 27-29. — ISBN 3-540-42624-8 .