Algoritmo de construcción de Glushkov

En la teoría de la informática —en particular en la teoría de lenguajes formales— el algoritmo de construcción de Glushkov , inventado por Victor Mikhailovich Glushkov , transforma una expresión regular dada en un autómata finito no determinista (AFN) equivalente. De este modo, establece un vínculo entre las expresiones regulares y los autómatas finitos no deterministas: dos representaciones abstractas de la misma clase de lenguajes formales .

Una expresión regular puede utilizarse para describir de forma práctica un patrón de búsqueda avanzado en una operación de "buscar y reemplazar" de un programa de procesamiento de texto . El algoritmo de Glushkov permite transformarla en un autómata finito no determinista (AFND), que además es pequeño por naturaleza, ya que el número de sus estados es igual al número de símbolos de la expresión regular, más uno. Posteriormente, el AFND puede hacerse determinista mediante la construcción del conjunto potencia y luego minimizarse para obtener un autómata óptimo que corresponda a la expresión regular dada. Este último formato es el más adecuado para su ejecución en un ordenador.

Desde otro punto de vista, más teórico, el algoritmo de Glushkov forma parte de la prueba de que tanto los autómatas finitos no deterministas (AFND) como las expresiones regulares aceptan exactamente los mismos lenguajes; es decir, los lenguajes regulares . El recíproco del algoritmo de Glushkov es el algoritmo de Kleene , que transforma un autómata finito en una expresión regular. El autómata obtenido mediante la construcción de Glushkov es el mismo que el obtenido mediante el algoritmo de construcción de Thompson , una vez eliminadas sus transiciones ε.

El algoritmo de construcción de Glushkov también se llama algoritmo de Berry-Sethi , llamado así en honor a Gérard Berry y Ravi Sethi, quienes trabajaron en esta construcción ^{[ 1 ]} .

Construcción

Dado una expresión regular $e$ , el algoritmo de construcción de Glushkov crea un autómata no determinista que acepta el lenguaje. $L(e)$ aceptado por $e$ . ^{[ 2 ]}^{[ 3 ]}^{: 59–61} La construcción utiliza cuatro pasos:

Paso 1

Linealización de la expresión. Cada letra del alfabeto que aparece en la expresión $e$ se renombra, de modo que cada letra aparece como máximo una vez en la nueva expresión. $e'$ La construcción de Glushkov se basa esencialmente en el hecho de que $e'$ representa un idioma local $L(e')$ . Sea $A$ el alfabeto antiguo y sea $B$ el nuevo.

Paso 2a

Cálculo de los conjuntos $P(e')$ , $D(e')$ , y $F(e')$ . La primera, $P(e')$ , es el conjunto de letras que aparece como primera letra de una palabra de $L(e')$ . El segundo, $D(e')$ , es el conjunto de letras que pueden terminar una palabra de $L(e')$ . El último, $F(e')$ , es el conjunto de pares de letras que pueden aparecer en palabras de $L(e')$ , es decir, es el conjunto de factores de longitud dos de las palabras de $L(e')$ Estos conjuntos se definen matemáticamente por

P(e')=\{x\in B\mid xB^{*}\cap L(e')\neq \emptyset \}

,

D(e')=\{y\in B\mid B^{*}y\cap L(e')\neq \emptyset \}

,

F(e')=\{u\in B^{2}\mid B^{*}uB^{*}\cap L(e')\neq \emptyset \}

.

Se calculan por inducción sobre la estructura de la expresión, como se explica a continuación .

Paso 2b

Cálculo del conjunto $\Lambda (e')$ que contiene la palabra vacía $\varepsilon$ si esta palabra pertenece a $L(e')$ y es el conjunto vacío en caso contrario. Formalmente, esto es $\Lambda (e')=\{\varepsilon \}\cap L(e')$ .

Paso 3

Cálculo del autómata que reconoce el idioma local , según lo definido por $P(e')$ , $D(e')$ , $F(e')$ , y $\Lambda (e')$ . Por definición, el lenguaje local definido por los conjuntos $P$ , $D$ y $F$ es el conjunto de palabras que comienzan con una letra de $P$ , terminan con una letra de $D$ y cuyos factores de longitud 2 pertenecen a $F$ , incluyendo opcionalmente también la palabra vacía; es decir, es el lenguaje:

L'=(PB^{*}\cap B^{*}D)\setminus B^{*}(B^{2}\setminus F)B^{*}\cup \Lambda (e')

.

En rigor, la construcción de Glushkov consiste en el cálculo del autómata para el lenguaje local denotado por esta expresión linealizada.

Paso 4

$Elimine la linealización, reemplazando cada letra B$ indexada por la letra $A$ original .

Ejemplo

Consideremos ^{[ 3 ]}^{: 64} la expresión regular $e=(a(ab)^{*})^{*}+(ba)^{*}$ .

La versión linealizada es
$e'=(a_{1}(a_{2}b_{3})^{*})^{*}+(b_{4}a_{5})^{*}$ .
Las cartas se han linealizado añadiéndoles un índice.
Los conjuntos $P$ , $D$ y $F$ de las primeras letras, últimas letras y factores de longitud 2 para la expresión lineal son respectivamente
${\begin{aligned}P(e')&=\{a_{1},b_{4}\}\\D(e')&=\{a_{1},b_{3},a_{5}\}\\F(e')&=\{a_{1}a_{2},a_{1}a_{1},a_{2}b_{3},b_{3}a_{1},b_{3}a_{2},b_{4}a_{5},a_{5}b_{4}\}\end{aligned}}$ .
La palabra vacía pertenece al lenguaje, por lo tanto $\Lambda (e')=\{\varepsilon \}$ .
El autómata del idioma local
$L'=(PB^{*}\cap B^{*}D)\setminus B^{*}(B^{2}\setminus F)B^{*}$
contiene un estado inicial, denotado por 1, y un estado para cada una de las cinco letras del alfabeto.
$B=\{a_{1},a_{2},b_{3},b_{4},a_{5}\}$ .
Hay una transición de 1 a los dos estados de $P$ , una transición de $x$ a $y$ para $xy\in F$ y los tres estados de $D$ son finales, y tal es el estado 1. Todas las transiciones a una letra $y$ tienen como etiqueta la letra $y$ .
Obtén el autómata para $L(e)$ eliminando los índices.

Cálculo del conjunto de letras

El cálculo de los conjuntos $P$ , $D$ , $F$ y $Λ$ se realiza inductivamente sobre la expresión regular. $e'$ Se deben proporcionar los valores de $\emptyset, ε$ (los símbolos para el lenguaje vacío y el lenguaje singleton que contiene la palabra vacía), las letras y los resultados de las operaciones. $+,\cdot ,^{*}$ .

Para $Λ$ , uno tiene
$\Lambda (\emptyset )=\emptyset$
$\Lambda (\varepsilon )=\{\varepsilon \}$
$\Lambda (a)=\emptyset$ por cada letra $a$
$\Lambda (e+f)=\Lambda (e)\cup \Lambda (f)$
$\Lambda (e\cdot f)=\Lambda (e)\cap \Lambda (f)$
$\Lambda (e^{*})=\{\varepsilon \}$
Para $P$ , uno tiene
$P(\emptyset )=P(\varepsilon )=\emptyset$
$P(a)=\{a\}$ por cada letra $a$
$P(e+f)=P(e)\cup P(f)$
$P(e\cdot f)={\begin{cases}P(e)\cup P(f)&{\text{si }}\Lambda (e){\text{ es }}\{\varepsilon \}\\P(e)&{\text{si }}\Lambda (e){\text{ es }}\emptyset \end{cases}}$
$P(e^{*})=P(e)$
Para $D$ , uno tiene
$D(\emptyset )=D(\varepsilon )=\emptyset$
$D(a)=\{a\}$ por cada letra $a$
$D(e+f)=D(e)\cup D(f)$
$D(e\cdot f)={\begin{cases}D(e)\cup D(f)&{\text{if }}\Lambda (f){\text{ is }}\{\varepsilon \}\\D(e)&{\text{if }}\Lambda (f){\text{ is }}\emptyset \end{cases}}$
$D(e^{*})=D(e)$
Para el conjunto de factores de longitud 2, se tiene
$F(\emptyset )=F(\varepsilon )=F(a)=\emptyset$ por cada letra $a$
$F(e+f)=F(e)\cup F(f)$
$F(e\cdot f)=F(e)\cup F(f)\cup D(e)\times P(f)$
$F(e^{*})=F(e)\cup D(e)\times P(e)$

Las operaciones más costosas son los productos cartesianos de conjuntos para el cálculo de $F.$

Propiedades

El autómata obtenido es no determinista y posee tantos estados como letras tenga la expresión regular, más uno. Se ha demostrado ^{[ 4 ]} que todo autómata de Thompson puede transformarse en un autómata de Glushkov mediante un método de eliminación de transiciones ε.

Aplicaciones y expresiones deterministas

El cálculo del autómata mediante la expresión se produce con frecuencia; se ha utilizado sistemáticamente en funciones de búsqueda, en particular por el comando grep de Unix . De manera similar, la especificación XML también utiliza construcciones similares; para mayor eficiencia, se han estudiado expresiones regulares de un tipo específico, denominadas expresiones deterministas . ^[⁵^]^[⁶^]

Véase también

Analista

Notas

↑ Berry y Sethi 1986 .
↑ VM Glushkov (1961). "La teoría abstracta de los autómatas" . Russian Mathematical Surveys . 16 (5): 1– 53. Bibcode : 1961RuMaS..16....1G . doi : 10.1070/rm1961v016n05abeh004112 . S2CID 250833514 .
1 2 Jean-Éric Pin (noviembre de 2016). Fundamentos matemáticos de la teoría de autómatas (PDF) . París: autoeditado.
↑ Giammarresi, Dora; Ponty, Jean-Luc; Wood, Deric (1998). "Construcciones de Gluskov y Thompson: Una síntesis" (PDF) . hdl : 1783.1/715 . Recuperado el 13 de julio de 2025 .
↑ Jacques Sakarovitch (2009). Elementos de la teoría de autómatas . Cambridge: Cambridge University Press. ISBN 9780521844253.
↑ Brüggemann-Klein, Anne (1993). "Expresiones regulares en autómatas finitos". Informática Teórica . 12 (2): 197– 213. doi : 10.1016/0304-3975(93)90287-4 .

Referencias

Berry, Gérard; Sethi, Ravi (1986), "De las expresiones regulares a los autómatas deterministas", Theoretical Computer Science , 48 : 117–126 , ISSN 0304-3975

Enlaces externos

Una construcción unificada de los autómatas de Glushkov, Follow y Antimirov

Algoritmos y Computación: 14º Simposio Internacional, ISAAC

[1] Berry y Sethi 1986 .

[2] VM Glushkov (1961). "La teoría abstracta de los autómatas" . Russian Mathematical Surveys . 16 (5): 1– 53. Bibcode : 1961RuMaS..16....1G . doi : 10.1070/rm1961v016n05abeh004112 . S2CID 250833514 .

[Pin.2016-3] 1 2 Jean-Éric Pin (noviembre de 2016). Fundamentos matemáticos de la teoría de autómatas (PDF) . París: autoeditado.

[4] Giammarresi, Dora; Ponty, Jean-Luc; Wood, Deric (1998). "Construcciones de Gluskov y Thompson: Una síntesis" (PDF) . hdl : 1783.1/715 . Recuperado el 13 de julio de 2025 .

[Sakarovitch.2009-5] Jacques Sakarovitch (2009). Elementos de la teoría de autómatas . Cambridge: Cambridge University Press. ISBN 9780521844253.

[6] Brüggemann-Klein, Anne (1993). "Expresiones regulares en autómatas finitos". Informática Teórica . 12 (2): 197– 213. doi : 10.1016/0304-3975(93)90287-4 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[

[