UNIÓN, CONCATENACIÓN Y ESTRELLA DE KLEENE DE LENGUAJES REGULARES
Sean los dos autómatas siguientes para el alfabeto
S = { x, y }:
1.- Unión de lenguajes
Para diseñar el autómata finito que admite el lenguaje unión aplicamos:
- Dibujamos un estado nuevo que va a ser el nuevo estado inicial y será de
aceptación si alguno de los estados iniciales de los diagramas originales lo era.
En nuestro caso el segundo diagrama original tiene un estado inicial que es de aceptación, con lo cual también lo será el nuevo estado. - Por cada uno de los arcos que hay desde los estados iniciales originales hacia otros (puede ser el mismo), se dibuja desde el nuevo estado inicial un arco hacia el estado destino del arco correspondiente en el diagrama original y se etiqueta con el mismo símbolo.
- A continuación se elimina la característica de inicio de los estados
iniciales originales.
2.- Concatenación de lenguajes
Para diseñar el autómata finito que admite el lenguaje concatenación aplicamos:
- Se dibuja el diagrama original de L1
- desde cada estado de aceptación del diagrama de L1 se dibuja un arco hacia cada estado de L2 que sea el destino de un arco del estado inicial de L2 y se rotula con el mismo símbolo
- Dejar que los estados de aceptación de L1 lo sean si el estado inicial
de L2 también lo es. Este es el caso del ejemplo, en caso contrario se
debería eliminar esta característica de todos los estados de aceptación de
L1.
3.- Estrella de Kleene
Para diseñar el autómata finito que admite el lenguaje concatenación aplicamos:
- Se añade al diagrama un nuevo estado que va a ser el de inicio y lo marcaremos como de aceptación
- Por cada uno de los arcos que hay desde el estado inicial original hacia otros
(puede ser el mismo), se dibuja desde el nuevo estado inicial un arco hacia el estado
destino del arco correspondiente en el diagrama original y se etiqueta con el mismo
símbolo
- Desde cada estado de aceptación se dibuja un arco por cada uno de los que salen desde el estado inicial original hacia otros (puede ser el mismo). Este sale hacia el estado destino del arco correspondiente que salía del estado inicial en el diagrama original y se etiqueta con el mismo símbolo.
- Se quita la característica de inicio del estado inicial original.
© 1999 Roberto de la Fuente López. Todos los derechos reservados
Fecha de actualización: 15 de abril de 1999