1 Autómatas finitos y expresiones regularesEstructuras de Datos

2 Autómatas finitos Es un modelo de computación Representa un lenguaje

3 Autómatas finitos Estados Alfabeto de entrada TransicionesConjunto finito Estados Transiciones Estados aceptados Estado inicial Alfabeto de entrada

4 Un estado recuerda que un evento importante ha sucedidoAutómatas finitos Un estado recuerda que un evento importante ha sucedido

5 Autómatas finitos Una transición representa una entrada, señal o evento en el sistema

6 Autómatas finitos

7 Autómatas finitos Las cadenas aceptadas terminan en 1 o en un número par de ceros después del último 1.

8 Autómatas finitos * Entradas 1 q1 q2 q3 Estados Tabla de transiciones

9 Autómatas finitos Dado un número en binario, decidir si es impar.

10 Minimización de autómatas finitosConsiste en eliminar los estados equivalentes del autómata

11 Minimización de autómatas finitosDos estados son distinguibles (diferentes) si: Uno es un estado aceptado y el otro no. Dada la misma entrada, los estados de llegada son distinguibles.

12 Minimización de autómatas

13 Minimización de autómatasB C D E F G x El estado aceptado se diferencia de todos los demás

14 Minimización de autómatasB C D E F G x X E se diferencia de A? Con la entrada cero, A pasa a B y E a D. B es distinguible de D, por lo tanto E es distinguible de A.

15 Minimización de autómatasB C D E F G x X E y C no se diferencian pues con la entrada 0 ambos van a D y con la entrada 1 van a F y B que aún no sabemos si son distinguibles.

16 Minimización de autómatasB C D E F G X x Los estados no distinguibles se vuelven uno solo.

17 Minimización de autómata

18 Minimización de autómata

19 Minimización de autómata

20 Minimización de autómatas

21 De autómata a expresión regularEliminar estados construyendo una expresión regular por cada “camino” que incluye el estado a eliminar

22 De autómata a expresión regularEliminar LR_2

23 De autómata a expresión regular

24 De autómata a expresión regular(R|SU*T)*SU*

25 De autómata a expresión regular: ejemplo

26 Ejercicio

27 Ejercicio Diseñar un autómata que dado un número en binario, indique si el número de ceros es divisible entre 3. Diseñar un autómata que dado un número en binario, indique si este es divisible entre 3. Diseñar un autómata que dado un número en binario, indique si este es divisible entre 5. Escribir las expresiones regulares de los autómatas anteriores.