Las expresiones regulares
describen los lenguajes regulares (aquellos reconocidos por autómatas
finitos).
Leyes algebraicas para
expresiones regulares
Construcción de
autómatas finitos a partir de expresiones regulares
Los lenguajes descriptos
por expresiones regulares son los lenguajes reconocidos por los autómatas
finitos. Existe un algoritmo para convertir una expresión regular
en el autómata finito no determinístico correspondiente.
El algoritmo construye a partir de la expresión regular un autómata
con transiciones vacías, es decir un autómata que contiene
arcos rotulados con .
Luego este autómata con transiciones vacías se puede convertir
en un autómata finito sin transiciones vacías que reconoce
el mismo lenguaje.
Si r tiene operadores, se
dan tres casos dependiendo de la forma de r:
Construcción
de la expresión regular a partir del autómata
A partir de cualquier autómata
finito es posible obtener una expresión regular que describe el
lenguaje reconocido por el autómata. Esta conversión consiste
en ir eliminando los estados del autómata uno por uno, reemplazando
los rótulos sobre los arcos, que inicialmente son símbolos,
por expresiones regulares más complicadas.
Eliminación de
estados del autómata
Se desea eliminar el estado
u, pero se deben mantener los rótulos de las expresiones regulares
sobre los arcos de modo tal que los rótulos de los caminos entre
cualesquier par de estados de los estados restantes no cambien.
Si no existe arco de u a
u se puede agregar uno rotulado .
Los nodos si,
para i = 1, 2, ..., n, son nodos predecesores del nodo u, y los nodos tj,
para j = 1, 2, ..., m, son nodos sucesores del nodo u.
Existe un arco de cada si
a u, rotulado por una expresión regular Si,
y un arco de u a cada tj
rotulado por una expresión regular Tj.
Si se elimina el nodo u, estos arcos y el arco rotulado U desaparecerán.
Para preservar estas cadenas, se debe considerar cada par si
y tj y agregar al
rótulo del arco de si
a tj, una expresión
regular que represente lo que desaparece.
En general se puede suponer
que existe un arco rotulado Rij
de si a tj para i
= 1, 2, ..., n y j = 1, 2, ..., m. Si el arco de si
a tj no está
presente se puede agregar con rótulo .
El conjunto de cadenas que
rotulan los caminos de si a u, incluyendo el ciclo de u a u, y luego de
u a tj, se puede describir por la expresión regular Si
U*
Tj.
Por lo tanto, después
de eliminar u y todos los arcos que llegan y salen de u, se debe reemplazar
el rótulo Rij
del arco de si a tj
por la expresión regular
Rij + Si
U* Tj
Algoritmo para construir
la expresión regular a partir del autómata
Los pasos a seguir son los
siguientes:
1) Repetir para cada estado
final:
2) Realizar la unión de las expresiones regulares obtenidas para cada estado final del autómata.