Dfa A Expresion Regular

CONVERSIÓN DE AUTÓMATAS FINITOS DETERMINISTICOS A EXPRESIONES REGULARES Investigación Por: Fernando David Irías Escher

1

CONTENIDO ¿Qué es un DFA? ................................................................................................................................................................ 3 ¿Qué es una Expresión Regular? ................................................................................................................................ 4 Operaciones de utilidad ................................................................................................................................................. 4 Método de la eliminación de estados ....................................................................................................................... 5 Ejemplo #1 ..................................................................................................................................................................... 6 Ejemplo #2 ................................................................................................................................................................. 11 Ejemplo #3 .................................................................................................................................................................. 15

2

INTRODUCCIÓN Se presenta la siguiente investigación realizada para la clase de Teoría de la Computación que se cursa el quinto período del año 2008. La misma consiste en la investigación, explicación y ejemplificación de un método para convertir Autómatas Finitos Determinísticos (DFAs) en Expresiones Regulares.

Al finalizar este informe, se espera que el lector tenga la capacidad de aplicar un método que le facilite la conversión de DFAs a Expresiones Regulares, por lo cual se le dará un marco teórico para comprender la nomenclatura que se utilizare a través del estudio. También se desarrollaran tres ejemplos utilizando el método seleccionado, los cuales se explicará paso a paso su resolución.

MARCO TEÓRICO ¿QUÉ ES UN DFA? Un Autómata Finito Determinístico (DFA) no es más que una máquina que consta de un conjunto finito de estados, de ahí el nombre de Máquina de Estados. Uno de estos estados debe ser la entrada de la máquina. En todo DFA debe existir uno o varios estados finales o de aceptación. Un DFA debe constar de un lenguaje (o símbolos de entrada) el cual es el conjunto de caracteres que aceptara dicha máquina. Todo DFA contiene un conjunto de transiciones. Cada estado debe tener una transición por cada símbolo que exista en el lenguaje. Estas transiciones deberán comunican un estado con otro (o se mantiene recursivos en el mismo estado). Una transición puede ser transitada si, y solo si, el símbolo de entrada que se está procesando es uno de los símbolos1 que permite el paso a través de la transición. Una cadena (o palabra) es una sucesión de símbolos que están contenidos dentro del lenguaje del autómata. Se dice que una cadena es aceptada cuando al haber consumido todos los símbolos contenidos en esta (por medio de las transiciones), se llega a un estado final o de aceptación.

1

Pueden ser Expresiones Regulares como veremos más adelante.

3

¿QUÉ ES UNA EXPRESIÓN REGULAR? Una Expresión Regular es una manera en que se puede representar una máquina de estados. Esta se considera más descriptiva que los DFAs, ya que presenta de una manera más legible para el humano el tipo de cadenas acepta la máquina. Se dice que los DFAs y las Expresiones Regulares son congruentes entre sí, ya que de ambas maneras se pueden representar una infinidad de Máquinas de Estados. Ya que estas se consideran congruentes, esta investigación se enfocara en demostrar que se puede hacer una conversión de un DFA a una Expresión Regular. Las Expresiones Regulares constan de tres operaciones básicas: 1. La unión: Se representa con el signo “más” (+). Si tenemos el conjunto A y el conjunto B, se podría decir que la unión de dichos conjuntos (A U B) se representa A + B en una Expresión Regular. 2. La concatenación: Se representa con un punto (.). Normalmente el punto no se escribe, y se toma como concatenación cuando se escriben de la forma “AB”, siendo A y B dos conjuntos. 3. La clausura (o clausura Kleene): Se representa con un asterisco (*) que se escribe seguido del conjunto al que se le aplica. Por ejemplo A*. Lo que la clausura nos indica es que habrán 0 ó más repeticiones de la cadena A.

OPERACIONES DE UTILIDAD Nos limitaremos a solo establecer algunas de las operaciones que nos serán útiles al momento de desarrollar la conversión2: 1. ‫ܮ‬ሺ∅∗ ሻ ≅ ሼℇሽ ܷ ‫ܮ‬ሺ∅ሻ ܷ ‫ܮ‬ሺ∅ሻ ܷ ‫ܮ‬ሺ∅ሻ … => ‫ܮ‬ሺ∅∗ ሻ ≅ ሼℇሽ => ∅∗ ≅ ℇ 2. ∅ܴ ≅ ܴ∅ ≅ ∅ 3. ∅ + ܴ ≅ ܴ + ∅ ≅ ܴ

2

Tomadas de Teoría de autómatas, lenguajes y computación de Hopcroft.

4

CONVERSIÓN DE UN DFA A UNA EXPRESIÓN REGULAR MÉTODO DE LA ELIMINACIÓN DE ESTADOS Básicamente este método consiste en seleccionar tres estados: ‫ݍ‬௥ , el cual no deberá ser ni el estado inicial, ni ninguno de los estados finales o de aceptación, también se deberá seleccionar un estado ‫ݍ‬௫ y ‫ݍ‬௬ , de manera que ‫ݍ‬௫ pueda llegar (por medio de transiciones) a ‫ݍ‬௬ utilizando a ‫ݍ‬௥ como estado intermedio entre estos. Después de haber seleccionado estos estados, se debe proceder a eliminar el estado ‫ݍ‬௥ , haciendo una transición que vaya de ‫ݍ‬௫ a ‫ݍ‬௬ y que por medio de la concatenación de las transiciones que llegan de ‫ݍ‬௫ a ‫ݍ‬௥ y salen de ‫ݍ‬௥ a ‫ݍ‬௬ (incluyendo las que hacen un bucle en ‫ݍ‬௥ ). En caso de que ya exista una transición que va de ‫ݍ‬௫ a ‫ݍ‬௬ , se hace la unión de la Expresión Regular de dicha transición con la Expresión Regular de la nueva transición antes creada. Esto se repite hasta que solo existan estados iniciales y finales en el DFA. Luego de tener la máquina de esta forma se debe generar la Expresión Regular a partir de ella. En el párrafo anterior se explico a groso modo (sin ningún detalle) como se debe reducir la máquina de estados, y también vimos que al reducirla la debemos transformar a una Expresión Regular. Ahora vamos a definir paso por paso y con detalle cómo se debe hacer la reducción. Veremos que al hacer la reducción se pueden dar tres casos en los que tendremos que generar la Expresión Regular de una manera ligeramente diferente. Para un mejor entendimiento de la eliminación de los estados utilizaremos el siguiente ejemplo:

5

EJEMPLO #1 Haremos la conversión del siguiente DFA a una Expresión Regular:

ILUSTRACIÓN 1: DFA ORIGINAL

PASO 1: Por cada transición ܳ௜ 3 que pueda ser recorrida con múltiples símbolos, se hará una transición ܳ௝ (siendo esta una transición que contiene una Expresión Regular)4 que contenga los símbolos de dicha transición ܳ௜ representados como una Expresión Regular, específicamente como una unión. APLICACIÓN: Como podemos observar, la transición que hace un bucle en ‫ݍ‬ଶ es la única transición que tiene múltiples símbolos con la cual puede ser transitada, por lo tanto la representaremos como una unión de la siguiente manera: a + b. Nos resulta en:

ILUSTRACIÓN 2: PASO 1

3 4

ܳ݅ representa el símbolo de la transición. A partir de este momento se tomaran todas las transiciones ܳ௜ como transiciones ܳ௝ .

6

PASO 2: Por cada estado ‫ݍ‬௜ , se debe verificar si hay una transición ܳ௝ que llegue a cada estado ‫ݍ‬௡ (donde ‫ݍ‬௡ = ‫ݍ‬௜ ) de la máquina. En caso de no existir esta transición se deberá agregar una transición que va desde ‫ݍ‬௜ hasta ‫ݍ‬௡ con el valor ∅. APLICACIÓN: Al aplicar el paso 2 a nuestro DFA, podemos ver que no hay transición de ‫ݍ‬଴ a ‫ݍ‬ଶ , tampoco existe un bucle en ‫ݍ‬ଵ , tampoco hay transición de ‫ݍ‬ଷ a ‫ݍ‬ଶ , etc. Por lo tanto agregaremos todas las transiciones que hacen falta para conectar cada estado con el resto de estados de la máquina. Estos estados tendrán el símbolo ø. Por lo tanto nuestro DFA resulta en:

ILUSTRACIÓN 3: PASO 2

PASO 3: Seleccionar un estado ‫ݍ‬௥ , talque ‫ݍ‬௥ NO sea un estado inicial y/o final. Luego, por cada estado ‫ݍ‬௫ se selecciona un camino, pasando por ‫ݍ‬௥ , hacia cada estado ‫ݍ‬௬ del DFA, talque ‫ݍ‬௫ ≠ ‫ݍ‬௥ y ‫ݍ‬௬ ≠ ‫ݍ‬௥ . Ahora se crea una transición ܳ௝ que tenga como Expresión Regular el símbolo (o Expresión Regular) de la transición que va de ‫ݍ‬௫ a ‫ݍ‬௥ concatenado con el símbolo de la transición que va de ‫ݍ‬௥ a ‫ݍ‬௬ . Al bucle que se hace en ‫ݍ‬௥ se le aplicará la operación de clausura (o clausura Kleene) y se concatenará con la Expresión Regular antes encontrada. A esta nueva transición ܳ௝ se le aplica una operación de unión con el símbolo de la transición que va de ‫ݍ‬௫ a ‫ݍ‬௬ . La transición ܳ௝ deberá quedar de la forma ܶ௜ ܵ ∗ ܶ௝ + ܶ௞ . Esta nueva transición ܳ௝ transitará del estado ‫ݍ‬௫ al estado ‫ݍ‬௬ .

7

APLICACIÓN: Ahora bien, seleccionaremos como estado ‫ݍ‬௥ a ‫ݍ‬ଵ . Haciendo la concatenación da cada transición desde todos los estados ‫ݍ‬௫ hacia todos los estados ‫ݍ‬௬ usando a ‫ݍ‬௥ como intermediario, nos resulta las siguientes Expresiones Regulares: ࢗ࢞ 0 0 0 2 2 2 3 3 3

ࡽ࢐

ࢗ࢟ 0 2 3 0 2 3 0 2 3

ܾܽ ܽØ ܽܽ ܾØ ܾØ ܽØ ܾØ ܾØ ܽØ

Ahora le aplicaremos la operación de clausura al bucle de ‫ݍ‬௥ y haremos la concatenación con el ܳ௝ que ya encontramos. Resulta en: ࢗ࢞ 0 0 0 2 2 2 3 3 3

ࡽ࢐

ࢗ࢟ 0 2 3 0 2 3 0 2 3

ܽØ∗ ܾ ܽØ∗ Ø ܽØ∗ ܽ ܾØ∗ Ø ܾØ∗ Ø ܽØ∗ Ø ܾØ∗ Ø ܾØ∗ Ø ܽØ∗ Ø

El siguiente paso es hacer la unión del ܳ௝ que ya tenemos con el símbolo de la transición que va de ‫ݍ‬௫ a ‫ݍ‬௬ directamente. También agregaremos una columna con la Expresión Regular ya simplificada, por lo tanto obtenemos: ࢗ࢞ 0 0 0 2 2 2 3 3 3

ࢗ࢟ 0 2 3 0 2 3 0 2 3

ࡽ࢐ ∗

ܽØ ܾ + ܾ ܽØ∗ Ø + Ø ܽØ∗ ܽ + Ø ܾØ∗ Ø + Ø ܾØ∗ Ø + ܽ + ܾ ܽØ∗ Ø + Ø ܾØ∗ Ø + ܾ ܾØ∗ Ø + ܽ ܽØ∗ Ø + Ø

8

Simplificación

ࢇ࢈ + ࢈ Ø ࢇࢇ Ø ࢇ+࢈ Ø ܾ ܽ Ø

Excelente! Hemos logrado eliminar el estado ‫ݍ‬ଵ de nuestro DFA. Ahora se deben seguir los mismos pasos hasta tener un DFA que solo contenga el estado inicial y los finales (en este caso ‫ݍ‬଴ y ‫ݍ‬ଶ ). El DFA nos queda de la siguiente manera:

ILUSTRACIÓN 4: PASO 3

Ahora que ya hemos comprendido los pasos esenciales de la eliminación de estados, presentaremos la tabla para eliminar el estado ‫ݍ‬ଷ : ࢗ࢞ 0

ࢗ࢟ 0

0 2 2

2 0 2

ࡽ࢐ ∗

ܽܽØ ܾ + ܾܽ +ܾ ܽܽØ∗ ܽ + Ø ØØ∗ ܽ + Ø ØØ∗ ܽ + ܾ + ܽ

Simplificación

ܾܽܽ + ܾܽ + ܾ ܽܽܽ Ø ܾ+ܽ

Hemos terminado de eliminar los estados no iníciales y no finales de nuestro DFA. Aplicando todas las Expresiones Regulares de la tabla anterior a nuestro DFA, nos quedaría así:

ILUSTRACIÓN 5: PASO 3

9

PASO 4: Si tenemos un estado inicial ‫ݍ‬௫ y un estado final ‫ݍ‬௬ donde ‫ݍ‬௫ ≠ ‫ݍ‬௬ , se debería generar una Expresión Regular a partir de este DFA de la forma ሺܴ + ܷܵ ∗ ܶሻ∗ ܷܵ ∗ , donde R es un bucle en ‫ݍ‬௫ , S es el camino que va de ‫ݍ‬௫ a ‫ݍ‬௬ , U es un bucle en ‫ݍ‬ଶ y T es el camino que va de ‫ݍ‬௬ a ‫ݍ‬௫ .

APLICACIÓN: Primero identificamos las Expresiones Regulares R, S, U y T. Tenemos que ܴ = ܾ + ܾܽ + ܾܽܽ, ܵ = ܽܽܽ, ܷ = ܽ + ܾ y ܶ = ∅. Ahora que ya tenemos los valores, procedemos a hacer la Expresión Regular final:

ࡱࡾ = ሺ࢈ + ࢇ࢈ + ࢇࢇ࢈ + ሺࢇࢇࢇሻሺࢇ + ࢈ሻ∗ ∅ሻ∗ ሺࢇࢇࢇሻሺࢇ + ࢈ሻ∗ = ሺ࢈ + ࢇ࢈ + ࢇࢇ࢈ሻ∗ ሺࢇࢇࢇሻሺࢇ + ࢈ሻ∗

10

EJEMPLO #2 Ahora presentaremos un nuevo ejemplo más corto, pero de mucha importancia, ya que el estado inicial y final son el mismo. Para resolver esto debemos hacer un paso preliminar antes de continuar. Todos los demás pasos se mantienen iguales.

ILUSTRACIÓN 6: DFA ORIGINAL

Antes de comenzar a reducir el DFA, debemos llevar a cabo un paso alternativo que nos permita separar el estado inicial y el estado final en dos estados distintos. PASO A1: Si existe un estado ‫ݍ‬௫ talque ‫ݍ‬௫ sea el estado inicial y un estado final, haremos un nuevo estado ‫ݍ‬௬ que pasara a ser el estado final y ‫ݍ‬௫ permanecerá solo como estado inicial. Se debe crear una transición ܳ௝ que tendrá como símbolo ߝ5. APLICACIÓN: Creamos un nuevo estado ‫ݍ‬ଷ y ponemos una transición que vaya de ‫ݍ‬଴ a ‫ݍ‬ଷ con el símbolo ߝ.

ILUSTRACIÓN 7: PASO A1

5

ߣ=ߝ

11

Una vez hecha la separación de los estados podemos proseguir con los pasos 1-4. Como podemos ver, cada transición de nuestro DFA tiene un símbolo único que le permite ser transitada, por lo tanto el paso 1 nos generará en mismo DFA de la ilustración 7. Aplicamos el paso 2 para poner todas las transiciones que nos hacen falta. Con esto obtenemos:

ILUSTRACIÓN 8: PASO 2

Esta es la tabla con las expresiones regulares ya simplificadas que nos resulta después de haber hecho el paso tres para el estado ‫ݍ‬ଵ : ࢗ࢞ 0 0 0 2 2 2 3 3 3

ࢗ࢟ 0 2 3 0 2 3 0 2 3

ࡽ࢐ 0 + 01 11 ߣ 1 + 00 01 ∅ ∅ ∅ ∅

12

A continuación el DFA que nos resulta al haber eliminado ‫ݍ‬ଵ :

ILUSTRACIÓN 9: PASO 3

Hacemos lo mismo para ‫ݍ‬ଶ , con esto tendremos solo estados iniciales y finales en nuestro DFA. La tabla de transiciones es:

ࢗ࢞ 0 0 3 3

ࢗ࢟ 0 3 0 3

ࡽ࢐

0 + 10 + 11ሺ01ሻ∗ ሺ1 + 00ሻ ߣ

Ø Ø

Al aplicar el paso tres a todos los estados no iniciales y no finales, obtenemos el siguiente DFA:

ILUSTRACIÓN 10: PASO 3

13

PASO A2: Si existe un estado ‫ݍ‬௫ inicial y ‫ݍ‬௬ final talque hay una transición ߣ entre estos estados, se deberá hacer una concatenación de las cerradura Kleene de las Expresiones Regulares que tienen la transición que hace bucle en ‫ݍ‬௫ , la transición que va de ‫ݍ‬௬ a ‫ݍ‬௫ y la transición que hace bucle en ‫ݍ‬௬ . A este conjunto se le aplicará la cerradura Kleeme y se le concatenará la cerradura Kleene de la transición que hace bucle en ‫ݍ‬௫ y la transición que hace bucle en ‫ݍ‬௬. APLICACIÓN: Al hacer la concatenación de las cerraduras Kleene de el bucle en ‫ݍ‬଴ , el bucle en ‫ݍ‬ଷ y la transición que va de ‫ݍ‬ଷ a ‫ݍ‬଴ nos queda le Expresión Regular: ∗ ∗

ሺ0 + 10 + 11ሺ01ሻ∗ ሺ1 + 00ሻሻ∗ Ø Ø Ahora le aplicamos la cerradura Kleene a este conjunto:

∗ ∗ ∗

ሺሺ0 + 10 + 11ሺ01ሻ∗ ሺ1 + 00ሻሻ∗ Ø Ø ሻ Proseguimos a concatenarlo con el bucle en ‫ݍ‬଴ y en ‫ݍ‬ଷ : ∗ ∗ ∗

∗

ሺሺ0 + 10 + 11ሺ01ሻ∗ ሺ1 + 00ሻሻ∗ Ø Ø ሻ ሺ0 + 10 + 11ሺ01ሻ∗ ሺ1 + 00ሻ∗ ሻ∗ Ø Al simplificar esta Expresion Regular nos queda: ሺ૙ + ૚૙ + ૚૚ሺ૙૚ሻ∗ ሺ૚ + ૙૙ሻሻ∗

14

EJEMPLO #3

Ahora haremos un nuevo ejercicio para reforzar los métodos aprendidos anteriormente. El siguiente DFA acepta cadena con un número par de 0´s y de 1´s:

ILUSTRACIÓN 11: DFA ORIGINAL

Creamos un nuevo nodo final ‫ݍ‬ସ con la transición ߣ que va desde ‫ݍ‬଴ hasta ‫ݍ‬ସ , nos resulta en:

ILUSTRACIÓN 12: PASO A1

15

Agregamos todas las transiciones ∅ para conectar cada estado con el resto de estados del DFA:

ILUSTRACIÓN 13: PASO 2

Ahora eliminaremos el estado ‫ݍ‬ଵ . Presentamos a continuación la tabla de transiciones y el DFA sin el estado ‫ݍ‬ଵ : ࢗ࢞ 0 0 0 0 2 2 2 2 3 3 3 3 4 4 4

ࡽ࢐ 00 1 01 ߣ 1 ∅ 0 ∅ 10 0 11 ∅ ∅ ∅ ∅

ࢗ࢟ 0 2 3 4 0 2 3 4 0 2 3 4 0 2 3

16

ILUSTRACIÓN 14: PASO 3

Ahora eliminaremos el estado ‫ݍ‬ଷ . Presentamos a continuación la tabla de transiciones y el DFA sin el estado ‫ݍ‬ଷ : ࢗ࢞ 0 0 0 2 2 2 4 4 4

ࡽ࢐ 00 + 01ሺ11ሻ ∗ 10 1 + 01ሺ11ሻ ∗ 0 ߣ 1 + 0ሺ11ሻ ∗ 10 0ሺ11ሻ ∗ 0 ∅ ∅ ∅ ∅

ࢗ࢟ 0 2 4 0 2 4 0 2 4

ILUSTRACIÓN 15: PASO 3

17

Ahora eliminaremos el estado ‫ݍ‬ଶ . Presentamos a continuación la tabla de transiciones y el DFA sin el estado ‫ݍ‬ଶ : ࢗ࢞ 0 0 4 4

ࢗ࢟ 0 4 0 4

ࡽ࢐ 00 + 01ሺ11ሻ ∗ 10 + ሺ1 + 01ሺ11ሻ ∗ 0ሻሺ0ሺ11ሻ ∗ 0ሻ ∗ ሺ1 + 0ሺ11ሻ ∗ 10ሻ ߣ ∅ ∅

ILUSTRACIÓN 16: PASO 3

Y para finalizar, generamos la Expresión regular final. La Expresión Regular ya simplificada es: ሺ૙૙ + ૙૚ሺ૚૚ሻ∗ ૚૙ + ሺ૚ + ૙૚ሺ૚૚ሻ∗ ૙ሻሺ૙ሺ૚૚ሻ∗ ૙ሻ∗ ሺ૚ + ૙ሺ૚૚ሻ∗ ૚૙ሻሻ∗

18