Análisis léxico. Lenguajes regulares y máquinas de estados finitos
por el número total de caracteres del alfabeto de símbolos y signos de operación y paréntesis en la entrada r.Base. Autómatas para expresiones de longitud 1: y se muestran en la siguiente figura.
Arroz. 5.1.
Tenga en cuenta que para cada uno de estos tres autómatas, el conjunto de estados finales consta de un solo estado.
Paso de inducción. Ahora supongamos que para cada expresión regular de longitud = 1, la palabra w se puede dividir en k subpalabras: w=w 1 w 2 ... w k y listo. Para cada i= 1,... ,k la palabra w i traduce q 0 1 en q f 1 . Entonces para la palabra w en el diagrama M hay un camino
Por eso, . Por el contrario, si alguna palabra traduce q 0 en q f , entonces existe o es llevada por un camino que, habiendo pasado de q 0 a q 0 1 y luego pasando varias veces por el camino de q 0 1 a q f 1 y regresando de q f 1 a q 0 1 por transición, finalmente de q f 1 por transición termina en q f . Por eso tal palabra.
De los teoremas 4.2 y 5.1 obtenemos directamente
Corolario 5.1. Para cada expresión regular, se puede construir efectivamente una máquina determinista de estados finitos que reconozca el lenguaje representado por esa expresión.
Esta afirmación es uno de los ejemplos de teoremas de síntesis: a partir de la descripción de una tarea (lenguaje como expresión regular), se construye efectivamente un programa (DFA) que la realiza. Lo contrario también es cierto: un teorema de análisis.
Teorema 5.2. Para cada máquina de estados finitos determinista (o no determinista), es posible construir una expresión regular que represente el lenguaje reconocido por esa máquina.
La demostración de este teorema es bastante técnica y está más allá del alcance de nuestro curso.
Por tanto, podemos concluir que la clase de lenguajes finitamente autómatas coincide con la clase de lenguajes regulares. De ahora en adelante lo llamaremos simplemente la clase de lenguajes de autómatas.
El autómata Mr, que se construye en la demostración del teorema 5.1
Definiciones básicas Las expresiones regulares en el alfabeto Σ y los conjuntos regulares que denotan se definen recursivamente de la siguiente manera: 1) – una expresión regular que denota un conjunto regular; 2) e – expresión regular que denota un conjunto regular (e); 3) si a Σ, entonces a es una expresión regular que denota un conjunto regular (a); 4) si p y q son expresiones regulares que denotan conjuntos regulares P y Q, entonces a) (p+q) es una expresión regular que denota P Q; b) pq – expresión regular que denota PQ; c) p* – expresión regular que denota P*; 5) nada más es una expresión regular.
Definiciones básicas Priorización: * (iteración) – máxima prioridad; concatenación; + (unión). Entonces 0 + 10* = (0 + (1 (0*))). Ejemplos: 1. 01 significa (01); 2. 0* – (0*); 3. (0+1)* – (0, 1)*; 4. (0+1)* 011 – significa el conjunto de todas las cadenas formado por 0 y 1 y que termina con la cadena 011; 5. (a+b) (a+b+0+1)* significa el conjunto de todas las cadenas (0, 1, a, b)* que comienzan con a o b.
Definiciones básicas del Lema: 1) α + β = β + α 2) * = e 3) α + (β + γ) = (α + β) + γ 4) α(βγ) = (αβ)γ 5) α( β + γ) = αβ + αγ 6) (α + β)γ = αγ + βγ 7) αe = eα = α 8) α = 9) α+α* = α* 10) (α*)* = α* 11) α+α = α 12) α+ = α
Relación entre RT y RM RM son lenguajes generados por RT. Por ejemplo: x = a+b, y = c+d, x X = (a, b), y Y = (c, d), x + y X Y = (a, b, c, d). Concatenación: xy XY = (ac, ad, bc, bd). k(u+o)t (k)(u, o)(t) = (ballena, gato) o por los Lemas No. 5 y No. 6 k(u+o)t = ballena + gato (ballena, gato) . Iteración: x = a, x* X* = (e, a, aaa,…), es decir, x* = e + xxx +…
Conexión entre RP y RM Iteración de concatenación y unión: (xy)* = e + xyxyxy + … (x + y)* = e + (x + y)(x + y) + … = = e + xx + xy + yx + yy + xxx +… Ejemplo: 0 + 1(0+1)* (0) ((1) (0, 1)*) = (0, 1, 10, 11, 100, 101, 110, 111… ). La unión es conmutativa: x + y = y + x La concatenación no es: xy ≠ yx
Comunicación entre RM y RM Ejemplos de prioridad: x + yz (x, yz), (x + y)z (xz, yz), x + y* (e, x, y, yyy, yyyy, ...), (x + y)* (e, x, y, xx, xy, yx, yy, xxx,…), (xy)* (e, xyxy,…), xy* (x, xyy, xyyy,…). Nuevos lemas: a* + e = a*; (a + e)* = a*; a*a* = a*; mi* = mi; etc.
Sistemas regulares de ecuaciones Ecuación con coeficientes regulares X = a. X + b tiene solución (punto fijo más pequeño) a*b: aa*b + b = (aa* + e)b = a*b Sistema de ecuaciones con coeficientes regulares: X 1 = α 10 + α 11 X 1 + α 12 X 2 + … + α 1 norte. Xn X 2 = α 20 + α 21 X 1 + α 22 X 2 + … + α 2 n. Xn…………………………. . Xn = αn 0 + αn 1 X 1 + αn 2 X 2 + … + αnn. Xn Incógnitas – Δ = (X 1, X 2,…, Xn).
Sistemas regulares de ecuaciones Algoritmo de solución (método de Gauss): Paso 1. Establezca i = 1. Paso 2. Si i = n, vaya al paso 4. De lo contrario, escriba las ecuaciones para Xi en la forma Xi = αXi + β (β = β 0 + βi +1 Xi+1 + … + βn.Xn). Luego, en el lado derecho de las ecuaciones Xi+1, ..., Xn, reemplazamos Xi con la expresión regular α*β. Paso 3. Incrementa i en 1 y regresa al paso 2. Paso 4. Escribe la ecuación para Xn como Xn = αXn + β. Vaya al paso 5 (con i = n). Paso 5. La ecuación para Xi es Xi = αXi + β. Escriba en la salida Xi = α*β, en las ecuaciones para Xi– 1, …, X 1, sustituyendo α*β en lugar de Xi. Paso 6. Si i = 1, deténgase; de lo contrario, disminuya i en 1 y regrese al paso 5.
Transformación de DFA en RT Para DFA M = (Q, Σ, δ, q 0, F) componemos un sistema con coeficientes regulares donde Δ = Q: 1. establecemos αij: = ; 2. si δ(Xi, a) = Xj, a Σ, entonces αij: = αij + a; 3. si Xi F o δ(Xi,) = HALT, entonces αi 0: = e. Después de resolver, el PV deseado será X 1 = q 0.
Conversión de DFA a RV Ejemplo: para un número de coma fija obtenemos el sistema q 0 = + q 0 + sq 1 + pq 2 + dq 3 + q 4 q 1 = + q 0 + q 1 + pq 2 + dq 3 + q 4 q 2 = + q 0 + q 1 + q 2 + q 3 + dq 4 q 3 = e + q 0 + q 1 + q 2 + dq 3 + pq 4 = e + q 0 + q 1 + q 2 + q 3 + dq 4 Aquí: s – signo del número, s = “+” + “–”; p – punto decimal, p = "."; d – números, d = “0” + “1” +… + “9”.
Conversión de DFA a RT Solución: q 0 = *(sq 1 + pq 2 + dq 3 + q 4 +) = sq 1 + pq 2 + dq 3 q 1 = + q 0 + q 1 + pq 2 + dq 3 + q 4 = pq 2 + dq 3, q 2 = + q 0 + q 1 + q 2 + q 3 + dq 4 = dq 4, q 3 = e + q 0 + q 1 + q 2 + dq 3 + pq 4 = dq 3 + pq 4 + e, q 4 = e + q 0 + q 1 + q 2 + q 3 + dq 4 = dq 4 + e. De la tercera ecuación: q 3 = dq 3 + pq 4 + e = d*(pq 4 + e). De la cuarta ecuación: q 4 = dq 4 + e = d*.
Conversión de DFA a RT Trazo inverso: q 3 = d*(pq 4 + e) = d*(pd* + e), q 2 = dq 4 = dd*, q 1 = pq 2 + dq 3 = pdd * + dd *(pd* + e), q 0 = sq 1 + pq 2 + dq 3 = s(pdd* + dd*(pd* + e)) + pdd* + dd*(pd* + e). Así, este DFA corresponde al RT s(pdd* + dd*(pd* + e)) + pdd* + dd*(pd* + e). Simplifiquemos: s(pdd* + dd*(pd* + e)) + pdd* + dd*(pd* + e) = = spdd* + sdd*(pd* + e) + pdd* + dd*(pd* + e) = (s + e)(pdd* + dd*(pd* + e)) Para una notación más corta, puedes usar la iteración positiva aa* = a*a = a+: (s + e)(pdd* + dd* (pd* + e)) = (s + e)(pd+ + d+pd* + d+)
Conversión de DFA a RT Mapeo del gráfico de la función de transición de DFA a operaciones básicas con expresiones regulares: q 0 a b a q 1 q 2 q 1 q 0 a+b a b ab q 2 a*
Conversión de DFA a RT Combinaciones de operaciones más complejas: q 0 a q 1 b b b q 0 a q 2 q 1 (a + e)b c b q 0 q 2 ab(cab)* q 0 (a + b)* q 0 a q 1 aa* = a+ q 0 a q 1 a b a a a (ab)+ q 2 b q 1 c e + (a + b)c*
Conversión de DFA a RT Para RT (s + e)(pd+ + d+(pd* + e)): q 0 p q 2 d s p q 1 d d q 3 d p q 4 d q 5 d
Programación RV Expresiones regulares: Integradas en muchos lenguajes de programación (PHP, Java. Script,...); Implementado como componentes de complemento (por ejemplo, la clase Regex para la plataforma .NET). Diferencias en las formas de notación: x? = x + e x(1, 3) = x + xxx, etc.
Programación RT Construcciones de la clase Regex (System. Text. Regular. Expressions): Símbolo Interpretación de la secuencia de escape b Cuando se usa entre corchetes, corresponde al símbolo “←” (u 0008) t, r, n, a, f, v Tab (u 0009), retorno de carro (u 000 D), nueva línea (u 000 A), etc. c. X Carácter de control (por ejemplo, c. C es Ctrl+C, u 0003) e Escape (u 001 B) ooo Carácter ASCII en octal xhh Carácter ASCII en hexadecimal uhhhh Carácter Unicode El siguiente carácter no es un carácter RT especial. Este símbolo debe usarse para escapar de todos los caracteres especiales. Ejemplo (el ejemplo muestra un patrón y una cadena de búsqueda, las coincidencias encontradas están subrayadas en la cadena): @"rnw+" – "rn. Hay dos líneas aquí".
Programación RV Subconjuntos de símbolos. Cualquier carácter excepto el final de la línea (n) Cualquier carácter del conjunto [^xxx] Cualquier carácter excepto los caracteres del conjunto Cualquier carácter del rango ] Restar un conjunto o rango de otro p(nombre) Cualquier carácter especificado por Unicode categoría denominada nombre P (nombre) Cualquier carácter distinto de los especificados por el nombre de categoría Unicode w El conjunto de caracteres utilizados para especificar identificadores W El conjunto de caracteres no utilizados para especificar identificadores s Espacios S Todos excepto espacios d Números D Sin dígitos Ejemplos : @". +" – "rn. Hay ndos líneas"; @"+" – "0 xabcfx"; @"[^fx]+" – "0 xabcfx"; @"+" – "0 xabcfx"; @"[^a-f]+" – "0 xabcfx"; @"]+" – "0 xabcfx"; @"p(Lu)" – "Luces de la ciudad"; // Lu – letras mayúsculas @"P(Lu)" – "Ciudad"; @"p(es. cirílico)" – "ja. OS"; //Es. Cirílico – letras rusas
Programación PB Anchor ^, A Al principio de la línea $, Z Al final de la línea o antes del carácter "n" al final de la línea z Al final de la línea G Donde termina la coincidencia anterior b Límite de palabra B Cualquier posición que no esté en el límite de una palabra. Ejemplos: @ "G(d)" – "(1)(3)(5)(9)"; // tres coincidencias (1), (2) y (3) @"bnS*ionb" – "donación de la nación"; @"Bendw*b" – "el final envía el prestamista duradero".
Programación de operaciones RT (cuantificadores) *, *? Iteración +, +? ¿Iteración positiva? , ? ? ¿Cero o una coincidencia (n), (n)? ¿Exactamente n coincide con (n, ), (n, )? ¿Al menos n coincidencias (n, m), (n, m)? De n a m coincidencias Ejemplos (los primeros cuantificadores son codiciosos, buscan tantos elementos como sea posible, los segundos son vagos, buscan la menor cantidad de elementos posible): @"d(3, )" – "888 -5555 "; @"^d(3)" – "913 -913"; @"-d(3)$" – "913 -913"; @"5+? 5" – "888 -5555"; // tres coincidencias: 55, 55 y 55 @"5+5" - "888 -5555".
Programación RV Agrupación () Un grupo que recibe automáticamente un número (? :) No guardar el grupo (?) o (? "nombre") Si se encuentra una coincidencia, se crea un grupo con nombre (?) o se elimina uno previamente definido grupo y (? "nombre - nombre") guardando en un nuevo grupo una subcadena entre un grupo previamente definido y un nuevo grupo (? imnsx:) Habilita o deshabilita cualquiera de las cinco (? –imnsx:) opciones posibles en un grupo: i – no distingue entre mayúsculas y minúsculas; s – una línea (luego “.” es cualquier carácter); m – modo multilínea (“^”, “$” – el principio y el final de cada línea); n – no capturar grupos sin nombre; x: excluye los espacios sin escape del patrón e incluye comentarios después del signo numérico (#) (? =) Una declaración de anticipación positiva de longitud cero
Programación RT (? !) Declaración de anticipación negativa de longitud cero (?) Parte no retornable (codiciosa) de una expresión Ejemplos: @"(an)+" – "bananas annals"; @"an+" – "anales de plátanos"; // comparar, tres coincidencias: an, an y ann @"(? i: an)+" - "ba. NAnas annals"; @"+(? =d)" – "abc xyz 12 555 w"; @"(?
Src="https://site/presentation/-112203859_437213351/image-24.jpg" alt="Número de enlaces de programación RV Enlace al grupo k Enlace al grupo nombrado Ejemplos: @"> Программирование РВ Ссылки число Ссылка на группу k Ссылка на именованную группу Примеры: @"(w)1" – "deep"; @"(? w)k " – "deep". Конструкции изменения | Альтернатива (соответствует операции объединения) (? (выражение)да|нет) Сопоставляется с частью «да» , если выражение соответствует; в противном случае сопоставляется с необязательной частью «нет» (? (имя)да|нет), Сопоставляется с частью «да» , если названное имя (? (число)да|нет) захвата имеет соответствие; в противном случае сопоставляется с необязательной частью «нет» Пример: @"th(e|is|at)" – "this is the day";!}
Programación de sustituciones RV $número Reemplaza la parte de la cadena correspondiente al grupo con el número especificado $(nombre) Reemplaza la parte de la cadena correspondiente al grupo con el nombre especificado $$ Sustituye $ $& Reemplaza con una copia del archivo completo match $` Reemplaza el texto de la cadena de entrada hasta que coincida con $" Reemplaza el texto de las líneas de entrada después de la coincidencia $+ Reemplaza el último grupo capturado $_ Reemplaza la línea completa Comentarios (? #) Comentario en línea # Comentario al final de la línea
Programación de resultados RT de Regex: Regex Matches() Coincidencia. Grupos de coincidencias de colección () Grupo. Capturas de grupo de colección() Captura. Capturas de colección()
Ejemplo de programación de RV en C++ CLI (Aplicación de consola Visual C++/CLR/CLR): int main() ( Regex ^r = gcnew Regex(L"((\d)+)+"); Match ^m = r-> Match (L"123 456"); int match. Count = 0; while (m->Éxito) ( Consola: : Write. Line(L"Match (0)", ++match. Count); for (int i = 1; i Grupos->Contar; i++) ( Grupo ^g = m->Grupos[i]; Consola: : Escribir. Línea(L" Grupo (0) = "(1)"", i, g-> Valor ); for (int j = 0; j Capturas->Contar; j++) ( Captura ^c = g->Capturas[j]; Consola: : Escribir. Línea(L" Captura (0) = "(1)" , posición = (2), longitud = (3)", j, c, c->Índice, c->Longitud); ) ) m = m->Next. Match(); ) return 0; ) Sistema: : Texto : : Regular. Expresiones
Habilitar acciones y encontrar errores Limitar el número de dígitos significativos de un número: (s + e)(pd+ + d+(pd* + e)) s = +|p = . d = d s + e = s? = (+|-)? pd* + e = (pd*)? = (.d*)? @"(+|-)? (. d+|d+(. d*)?)" o @"^(+|-)? (. d+|d+(. d*)?)$" Regex r = nueva expresión regular (@"^(+|-)? (. (? "dígito"d)+|(? "dígito"d)+(. (? "dígito"d)*)?)$"); Coincidir m = r. Coincidencia("+1. 23456789"); if (m. Éxito) ( Grupo g = m. Grupos["dígito"]; if (g. Capturas. Contar
Habilitación de acciones y búsqueda de errores Determinación de la posición del error: Regex r = new Regex(@"(+|-)? (. (? "digit"d)+|(? "digit"d)+(. (? "digit" d )*)?)"); cadena cadena = "+1. 2345! 678"; Coincidir m = r. Coincidencia(cadena); if (m. Success) ( Group g = m. Groups["dígito"]; if (g. Captures. Count 0) Console. Write. Line("Error en la posición 1: carácter inesperado "(0)"", str ); en caso contrario (m. Longitud
Habilitación de acciones y búsqueda de errores Determinación de la posición del error: 1. la primera posición de la cadena de entrada (1), si la primera coincidencia no comienza desde la posición Índice = 0; 2. la posición siguiente a la última coincidencia (coincidencia. Longitud + 1), si no coincide con la última posición de la cadena de entrada; 3. posición del primer espacio entre coincidencias (coincidencia[i]. Índice + coincidencia[i]. Longitud + 1), si el carácter que sigue a la coincidencia anterior no es el primer carácter de la siguiente coincidencia.
Índice) romper; índice = m[i]. Índice + m[i]. Longitud; ) Consola. Escribir. Line("Error en la posición (0) "(1)"", índice + 1, cadena); ) "a B C. xyz. pqr" – correcto; "+abc. xyz. pqr” – error en la posición 1 (“+”); "a B C. xyz. pqr! – error en la posición 12 (“!”); "a B C. xyz!. pqr" – error en la posición 8 (“!”).
Habilitación de acciones y búsqueda de errores ¡Pero! "a B C. xyz. +pqr” – error en la posición 8 (“.”). Nueva opción de plantilla: @"w+(. w+)*(. (? !$))? " Validación: "abc. xyz. +pqr” – error en la posición 9 (“+”); "a B C. xyz. pqr. " – error en la posición 12 (".").
Definiciones equilibradas: "(? "x")" agrega un elemento a la colección denominada "x"; “(? “-x)” elimina un elemento de la colección “x”; "(? (x)(? !))" comprueba que no quedan elementos en la colección "x". Lenguaje L que describe los operadores anidados de Pascal “comienzo fin; ": @"^s*((? "comienza+)+(? "-comienza"termina*; s*)+)*(? (comienza)(? !))$".
Es más conveniente describir el vocabulario de un idioma en forma de expresiones regulares y reconocer el idioma mediante CA. Por lo tanto, es importante poder convertir definiciones de lenguaje en forma de expresiones regulares en una definición en forma de CA. Esta transformación fue propuesta por Kenneth Thompson.
La máquina de estados finitos es cinco (S, S, d, S 0 , F)
S es un conjunto finito de estados.
S es un conjunto finito de señales de entrada válidas.
d - función de transición. Refleja el conjunto Sx(SÈ(e)) en el conjunto de estados de un autómata finito no determinista. Para un autómata determinista, la función de transición refleja el conjunto SxS en el conjunto de estados del autómata. En otras palabras, dependiendo del estado y del símbolo de entrada, d determina el nuevo estado de la máquina.
S 0 - estado inicial del autómata finito, S 0 О S.
F es el conjunto de estados finales del autómata, F О S.
El funcionamiento de una máquina de estados finitos es una secuencia de pasos. El paso está determinado por el estado de la máquina y el símbolo de entrada. El paso en sí consiste en cambiar el estado de la máquina y leer el siguiente símbolo de la secuencia de entrada.
Existen las siguientes reglas para convertir expresiones regulares en una máquina de estados.
1 La expresión regular “e” se transforma en un autómata de dos estados y una transición electrónica entre ellos (Figura 1).
Figura 1. – Máquina automática para la transición electrónica
2 Una expresión regular de un carácter "a" se convierte en un autómata finito de dos estados y una transición entre ellos en función de la señal de entrada a (Figura 2).
Figura 2. – Máquina automática de desplazamiento mediante símbolo a
3 Sea una expresión regular rs y máquinas de estados finitos para la expresión r y la expresión s ya se han construido. Luego se conectan dos máquinas en serie. La Figura 3 muestra los autómatas originales para los idiomas r y s. La figura muestra un autómata para reconocer la concatenación de estos idiomas.
Máquina para r Máquina para s
Figura 3. – Autómatas iniciales
Figura 4. – Máquina de concatenación de idiomas
4 Sea una expresión regular r | s y máquinas de estados finitos ya se han construido para la expresión r y la expresión s (Figura 3). Entonces el autómata resultante debe tener una alternativa a la ejecución de uno de los dos autómatas. Es decir, un autómata para la expresión r | s para autómatas para r y s de la Figura 3 tiene la forma que se muestra en la Figura 5.
Figura 5.- Máquina automática de combinación de idiomas
5 Sea una expresión regular r* para el autómata finito construido r. En este caso, se introducen dos nuevos estados para hacer posible omitir la expresión autómata r, y también introducir una transición electrónica entre los estados final e inicial para hacer posible repetir el autómata r varias veces. Si para la expresión regular r se construye un autómata similar a la Figura 3, entonces la expresión regular r* corresponde al autómata finito presentado en la Figura 6.
Ajustes
Según el teorema de Kleene, cualquier expresión regular se puede asociar una máquina finita, que es un modelo formal de un algoritmo para reconocer lexemas indicados por una expresión regular determinada. En términos más generales, una máquina de estados-el reconocedor está determinado por un conjunto finito de estados característicos del flujo de entrada y las transiciones entre ellos. Se produce un cambio de estado cuando los símbolos del flujo de entrada se reciben de un alfabeto determinado de acuerdo con la función de transición., que determina posibles estados posteriores en función del símbolo de entrada y el estado actual. Entre los posibles estados destaca el inicial(inicial) y final(permitiendo) estados en los que el reconocedor de autómatas finito puede estar, respectivamente, al comienzo y al final del procesamiento de tokens del flujo de entrada. Si la secuencia de entrada de símbolos puede generar una secuencia de transiciones que pueden transferir la máquina de estados finitos desde el estado inicial a uno de los estados finales, entonces se considera admitida y pertenece al conjunto regular reconocido por ella.
(00|11)*((01|10)(00|11)*(01|10)(00|11)*)*
tabla 1
| 0 | 1 | |
| Q1 | Q4 | Q2 |
| Q2 | Q3 | Q1 |
| Q3 | Q2 | Q4 |
| Q4 | Q1 | Q3 |
Las columnas de la tabla de transición indican los caracteres del alfabeto de entrada y las filas corresponden a los estados actuales del DFA.. Los elementos de cada línea indican los estados del DFA., al cual debe pasar del estado actual al recibir los caracteres correspondientes del alfabeto de entrada. En particular, de la primera línea de esta tabla de transición se deduce que recibir los símbolos 0 y 1 en el estado inicial Q1 traduce el DFA a los estados Q4 y Q2, respectivamente.
Al reconocer una secuencia de entrada utilizando la tabla de transición, es fácil rastrear cambios en el estado del DFA para determinar si se alcanza o no uno de los estados permitidos. En particular, para el vector binario 01001000 con un número par de ceros y unos, el DFA considerado genera la siguiente secuencia de transiciones, donde cada transición está etiquetada por el símbolo del alfabeto de entrada que la causa:
T1 0 T4 1 T3 0 T2 0 T3 1 T4 1 T1 0 T4 0 T1
Esta secuencia de transiciones termina con el estado de admisión Q1, por lo tanto, el vector binario 01001000 pertenece al conjunto regular reconocido por el DFA considerado. y satisface la expresión regular anterior.
En conclusión, cabe señalar que el método informal considerado de construcción
Para estudiar más a fondo las propiedades de los autómatas finitos y, en particular, para resolver el problema de síntesis, el siguiente teorema es importante.
Teorema 7.7 (teorema de determinación). Para cualquier autómata finito, se puede construir un autómata finito determinista equivalente.
Para demostrar el teorema, es necesario, en primer lugar, describir el algoritmo para construir un autómata finito determinista a partir del original; en segundo lugar, justificar este algoritmo demostrando rigurosamente que efectivamente produce una máquina de estados que es determinista y equivalente a la original. Aquí presentamos sólo el algoritmo para construir un autómata determinista.
La transformación de un autómata finito arbitrario en uno determinista equivalente se lleva a cabo en dos etapas: primero, se eliminan los arcos con la etiqueta \lambda y luego se lleva a cabo la determinización misma.
1. Eliminación de transiciones λ (arcos etiquetados \lambda).
Para pasar del autómata finito original M=(V,Q,q_0,F,\delta) al autómata finito equivalente M"=(V,Q",q_0,F",\delta") sin λ-transiciones, Es suficiente en el original realizar las siguientes transformaciones en el gráfico M.
A. Se eliminan todos los estados, excepto el inicial, en el que sólo entran los arcos con la etiqueta \lambda; definiendo así el conjunto Q" del autómata finito M". Está claro que Q"\subseteq Q. Al mismo tiempo, suponemos que el estado inicial sigue siendo el mismo.
b. El conjunto de arcos del autómata finito M" y sus etiquetas (por lo tanto, la función de transición M" ) se define de la siguiente manera: para dos estados cualesquiera p,r\in Q",~ p\to_(a)r ocurre si y sólo si a \en V , y en el gráfico M se cumple una de dos cosas: o hay un arco de p a r cuya etiqueta contiene el símbolo a, o hay un estado q tal que p\Rightarrow_(\lambda)^( +)q y q\ to_(a)r En este caso, el vértice q, en términos generales, puede no pertenecer al conjunto Q", es decir puede desaparecer al pasar al autómata M" (Fig. 7.11). Si q\en Q" , entonces, naturalmente, el arco (q,r) se conservará en M" y el símbolo a será uno de los símbolos perteneciente a la etiqueta de este arco (Fig. 7.12).
Así, en M" se almacenan todos los arcos M cuyas etiquetas son diferentes de \lambda y que conectan un par (vértices) de estados del conjunto Q" (no eliminados según el inciso a). Además, para cualquier triple de estados p,q,r (¡no necesariamente diferentes!), tal que p,r\en Q" y hay un camino de longitud distinta de cero de p a q, cuya etiqueta es igual a \lambda (es decir, el camino por transiciones λ), y un arco va de q a r, cuya etiqueta contiene el símbolo a del alfabeto de entrada, en M" se construye un arco de p a r, la etiqueta de que contiene el símbolo a (ver Fig. 7.11).
v. El conjunto de estados finales F" del autómata finito M" contiene todos los estados q\en Q", es decir, estados del autómata finito M que no se eliminan según el párrafo a, para los cuales q\Rightarrow_(\lambda)^(\ ast) mantiene q_f para algún q_f\in F (es decir, el estado q en sí mismo es el estado final del autómata finito M, o un camino de longitud distinta de cero conduce desde él a lo largo de arcos etiquetados \lambda hasta uno de los estados finales del autómata finito M) (figura 7.13).
2. Determinación misma.
Sea M=(Q,V,q_0,F,\delta) un autómata finito sin λ-transiciones. Construyamos un autómata finito determinista M_1 equivalente a M.
Este autómata finito se define de tal manera que su conjunto de estados es el conjunto de todos los subconjuntos del conjunto de estados del autómata finito M. Esto significa que cada estado individual del autómata finito M_1 se define como un subconjunto determinado del conjunto de estados del autómata finito M. En este caso, el estado inicial de la nueva máquina de estados finitos (es decir, M_1) es un subconjunto singleton que contiene el estado inicial de la antigua máquina de estados finitos (es decir, M), y los estados finales de la nueva máquina de estados finitos son todos esos subconjuntos. Q que contienen al menos un vértice final del autómata finito original M.
De ahora en adelante, permitiendo cierta libertad de expresión, a veces llamaremos a los estados del autómata finito M_1 conjuntos de estados. Sin embargo, es importante comprender claramente que cada conjunto de estados es un estado separado de un nuevo autómata finito, pero no un conjunto de sus estados. Al mismo tiempo, para el autómata finito original ("antiguo") M este es precisamente el conjunto de sus estados. En sentido figurado, cada subconjunto de estados del antiguo autómata finito se “colapsa” en un estado del nuevo autómata finito*.
*Formalmente, deberíamos definir el conjunto Q_1 como un conjunto que está en correspondencia uno a uno con el conjunto 2^Q, pero aún es más conveniente para nosotros suponer que Q_1 coincide con 2^Q; después de todo, el conjunto Q_1 coincide con 2^Q. El conjunto de estados de un autómata finito puede ser cualquier conjunto finito no vacío.
La función de transición del nuevo autómata finito se define de modo que desde el conjunto de estados S por el símbolo de entrada a, el autómata finito M_1 pasa al conjunto de estados, que es la unión de todos los conjuntos de estados del antiguo autómata finito en los que este viejo autómata finito se conoce con el símbolo a de cada conjunto de estados S. Por tanto, el autómata finito M_1 es determinista por construcción.
La descripción verbal anterior se puede traducir en fórmulas de la siguiente manera: construimos una máquina finita M_1 de modo que
M_1=(Q_1,V,\(q_0\),F_1,\delta_1), donde
\begin(cases)Q_1=2^Q,\quad F_1=\(T\colon\, T\cap F\ne\varnothing,~T\in2^Q\),\\ (\forall S\subseteq Q) (\forall a\in V)\Bigl(\delta_1(S,a)= \bigcup\limits_(q\in S)\delta(q,a)\Bigr). \end(casos)
Prestemos atención al hecho de que entre los estados del nuevo autómata finito hay un estado \varnothing y, según (7.8), \delta_1(\varnothing,a)=\varnothing para cualquier símbolo de entrada a . Esto significa que, una vez en dicho estado, la máquina de estados M_1 no lo abandonará. En general, cualquier estado q de un autómata finito tal que para cualquier símbolo de entrada a tengamos \delta(q,a)=q se denomina estado absorbente del autómata finito. Por lo tanto, el estado \varnothing de la máquina determinista de estados finitos M_1 es absorbente. También es útil señalar que \delta_1(S,a)=\varnada si y sólo si para cada q\in S (estados de la antigua máquina de estados finitos del conjunto de estados S ) \delta(q,a)= \varnada, es decir, e. en el gráfico M, no sale ningún arco de cada estado q, marcado con el símbolo a.
Se puede demostrar que el autómata finito obtenido utilizando dicho algoritmo es equivalente al original.
Ejemplo 7.9. Determinemos el autómata finito que se muestra en la figura. 7.14.
En la figura 2 se muestra un autómata finito equivalente sin transiciones λ. 7.15. Tenga en cuenta que el vértice q_2 desaparece, ya que sólo entran en él arcos “vacíos”.
Para determinar el autómata resultante, no es necesario escribir todos sus 2^3=8 estados, muchos de los cuales pueden no ser accesibles desde el estado inicial \(q_0\) . Para obtener estados a los que se puede acceder desde \(q_0\), y solo a ellos, usaremos el llamado método de extracción.
Este método generalmente se puede describir de la siguiente manera.
En el autómata finito inicial (sin arcos vacíos) definimos todos los conjuntos de estados que son alcanzables desde el inicial, es decir para cada símbolo de entrada a encontramos el conjunto \delta(q_0,a) . Cada uno de estos conjuntos en el nuevo autómata es un estado directamente accesible desde el inicial.
Para cada uno de los conjuntos de estados definidos S y cada símbolo de entrada a, encontramos el conjunto \textstyle(\mathop(\bigcup\limits_(q\in S) \delta(q,a))\limits^(\phantom( A)^( .))) . Todos los estados obtenidos en este paso serán estados de un nuevo autómata (determinista), accesible desde el vértice inicial a lo largo de un camino de longitud 2. Repetimos el procedimiento descrito hasta que no aparezcan nuevos estados establecidos (¡incluido el vacío!). Se puede demostrar que esto produce todos los estados del autómata finito M_1 que son alcanzables desde el estado inicial \(q_0\).
Para la máquina de estados finitos de la Fig. 7.15 tenemos:
\begin(alineado)& \delta_1(\(q_0\),a)=\(q_1\);\qquad \delta_1(\(q_0\),b)=\(q_1,q_3\);\\ & \ delta_1(\(q_1\),a)=\(q_1\);\qquad \delta_1(\(q_1\),b)=\(q_1\);\\ & \delta_1(\(q_1,q_3\) ,a)= \delta(q_1,a)\cup \delta(q_3,a)= \(q_1\)\cup\(q_1\)=\(q_1\);\\ & \delta_1(\(q_1, q_3\),b)= \delta(q_1,b)\taza \delta(q_3,b)= \(q_1\)\taza\(q_1\)=\(q_1\). \end(alineado)
Como no han aparecido nuevos conjuntos de estados, el procedimiento de “tirar” termina aquí y obtenemos el gráfico que se muestra en la figura. 7.16.
Adición regular de idiomaUna de las consecuencias teóricas importantes del teorema de determinización es el siguiente teorema.
Teorema 7.8. El complemento de un lenguaje regular es un lenguaje regular.
Sea L un lenguaje regular del alfabeto V. Entonces el complemento del lenguaje L (como un conjunto de palabras) es el lenguaje \overline(L)=V^(\ast)\setminus L .
Según el teorema 7.7, para un lenguaje regular L, se puede construir un autómata finito determinista M que admita L. Dado que en un autómata determinista desde cada vértice para cada símbolo de entrada se define una transición a exactamente un vértice, entonces cualquiera que sea la cadena x en el alfabeto V, hay una ruta única para ella en M, comenzando en el estado inicial en el que Se lee la cadena x. Está claro que la cadena x está permitida por el autómata M , es decir, x\in L(M) , si y sólo si el último estado de la ruta especificada es final. De ello se deduce que la cadena x\notin L(M) si y sólo si el último estado de la ruta especificada no es final. Pero sólo necesitamos un autómata finito M" que admita una cadena x si y sólo si no lo permite el autómata finito original M. Por lo tanto, convirtiendo cada estado final de M en un estado no final y viceversa, obtenemos un Autómata determinista que admite la adición del lenguaje L.
El teorema demostrado nos permite construir un autómata finito que no admite un determinado conjunto de cadenas, utilizando el siguiente método: primero construimos un autómata que admite un determinado conjunto de cadenas, luego lo determinamos y vamos al autómata para sumar como indicado en la demostración del teorema 7.8.
Ejemplo 7.10. A. Construyamos un autómata finito que acepte todas las cadenas del alfabeto \(0;1\) excepto la cadena 101.
Primero, construyamos un autómata finito que permita una sola cadena 101. Este autómata se muestra en la Fig. 7.17.
Este autómata es cuasi-determinista, pero no determinista, ya que no está completamente definido. Determinémoslo y obtengamos un autómata finito equivalente determinista como se muestra en la figura. 7.18.
Y finalmente, pasando a la suma (y cambiando el nombre de los estados), obtenemos el autómata que se muestra en la Fig. 7.19.
Tenga en cuenta que en el autómata resultante todos los vértices, excepto el vértice s_3, son finales.
Obsérvese también que la transición al complemento, que se analiza en la demostración del teorema 7.8, sólo puede llevarse a cabo en un autómata determinista. Si tuviéramos que intercambiar los roles de los vértices finales y no finales en el autómata mostrado en la Fig. 7.17, entonces obtendríamos un autómata que admite el lenguaje \(\lambda,1,10\) , que no es, como se puede imaginar fácilmente, el conjunto de todas las cadenas distintas de la cadena 101.
Tenga en cuenta también que la máquina de estados finitos de la Fig. 7.19 permite todas las cadenas que contienen una aparición de la cadena 101 pero que no coinciden con esa cadena en sí. Aquí, por ejemplo, está el camino que lleva la cadena 1011: s_0,s_1,s_2,s_3,t.
b. Construyamos un autómata finito que acepte todas las cadenas del alfabeto \(0;1\) excepto aquellas que contienen una ocurrencia de la cadena 101. Consideremos un lenguaje L, cada cadena del cual contiene una ocurrencia de la cadena 101. Puede ser definido de la siguiente manera:
L=(0+1)^(\ast)101(0+1)^(\ast).
Necesitamos construir un autómata para complementar el lenguaje L.
En este caso, utilizando directamente la expresión regular, es fácil construir un autómata finito que acepte el lenguaje L (figura 7.20).
Luego realizaremos la determinación mediante el método “pull”. El resultado de la determinación se presenta en la Fig. 7.21.
Para resolver completamente el problema, todo lo que queda está en la Fig. 7.21 intercambie los roles de los vértices finales y no finales (Fig. 7.22).
v. Analicemos la idea de construir un autómata finito que permita aquellas y sólo aquellas cadenas en el alfabeto \(0;1\) que no comienzan con la cadena 01 y no terminan con la cadena 11 (es decir, cadenas del formulario 01x y cadenas del tipo y11 no están permitidas, cualquiera que sea la cadena x,y\in\(0;1\) ).
En este caso, el complemento del lenguaje para el cual es necesario construir un autómata finito es el conjunto de todas esas cadenas de ceros y unos que comienzan con la cadena 01 o terminan con la cadena 11. Un autómata que permite este conjunto de chains se construye como un autómata para combinar 01(0+1)^(\ ast)+(0+1)^(\ast)11 de la misma manera que se describe en la prueba del teorema de Kleene (ver Teorema 7.6).
De la propiedad de que la clase de lenguajes regulares está cerrada con respecto al complemento (ver Teorema 7.8), se deduce inmediatamente que esta clase está cerrada con respecto a la intersección, la teoría de conjuntos y la diferencia simétrica.
Corolario 7.3. Para dos lenguajes regulares cualesquiera L_1 y L_2, las siguientes afirmaciones son verdaderas:
1) la intersección de L_1\cap L_2 es regular;
2) la diferencia L_1\setminus L_2 es regular;
3) la diferencia simétrica L_1\vartriangle L_2 es regular.
La validez de las declaraciones se desprende de las identidades:
\begin(alineado) &(\scriptstyle(\mathsf(1))))\quad L_1\cap L_2= \overline(\overline(L_1) \cup\overline(L_2))\,;\\ &(\scriptstyle (\mathsf(2))))\quad L_1\setminus L_2= L_1\cap \overline(L_2)\,;\\ &(\scriptstyle(\mathsf(3))))\quad L_1\,\triangle\ ,L_2 = (L_1\cup L_2)\setminus (L_1\cap L_2).\end(alineado)
En primer lugar, los resultados obtenidos permiten afirmar que la clase de lenguajes regulares respecto de las operaciones de unión, intersección y suma es un álgebra booleana, en la que la unidad es el lenguaje universal, y el cero es el lenguaje vacío. En segundo lugar, estas propiedades algebraicas de la familia de lenguajes regulares nos permiten resolver el importante problema de reconocer la equivalencia de dos autómatas finitos arbitrarios.
Según la Definición 7.10, las máquinas de estados finitos son equivalentes si los lenguajes que aceptan son los mismos. Por tanto, para verificar la equivalencia de los autómatas M_1 y M_2, basta con demostrar que la diferencia simétrica de los lenguajes L(M_1) y L(M_2) está vacía. Para ello, a su vez, basta con construir un autómata que admita esta diferencia y asegurarse de que el lenguaje que admite esté vacío. En general, el problema de reconocer que el lenguaje de una máquina de estados está vacío se denomina problema de vacuidad de la máquina de estados. Para resolver este problema basta con encontrar el conjunto de estados finales del autómata alcanzables desde el estado inicial. Dado que una máquina de estados finitos es un gráfico dirigido, este problema se puede resolver, por ejemplo, mediante la búsqueda en amplitud. Un lenguaje permitido por una máquina de estados finitos está vacío si y sólo si el conjunto de estados finales alcanzables desde el estado inicial está vacío. En la práctica, es preferible reconocer la equivalencia de autómatas finitos utilizando un algoritmo de minimización, pero ahora es importante para nosotros enfatizar que la posibilidad fundamental de resolver el problema de equivalencia se deriva del Teorema 7.7 y sus consecuencias algebraicas.
