Expresiones Regulares

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:

  •  Si el estado final es también inicial, eliminar todos los estados excepto el estado inicial.


  •       La expresión regular correspondiente es S*.
     
  •  Sino, eliminar los estados del autómata hasta que queden únicamente el estado inicial y el estado final en consideración.


  •      La expresión regular que nos lleva del estado s al estado t es
                       S* U (T + V S* U)*  @ S* U (T* (V S* U)*)*

    2) Realizar la unión de las expresiones regulares obtenidas para cada estado final del autómata.