Automatas Finitos Y Expresiones Regulares

07/09/2010

Definición y ejemplos de AFN AFD

Expresiones regulares

1

07/09/2010

Ejemplos

Propiedades de las Expresiones regulares

2

07/09/2010

Equivalencia AutómatasExpresiones Regulares

Transformación de una expresión regular a un autómata finito
• Dada una expresión regular existe un autómata finito capaz de reconocer el lenguaje que ésta define. • Dado unautómata finito, se puede expresar mediante una expresión regular el lenguaje que reconoce.

3

07/09/2010

Equivalencia entre expresiones regulares básicas y autómatas finitos
• Expresión regular λ

Equivalencia entre expresiones regulares básicas y autómatas finitos
• Expresión regular a

4

07/09/2010

Equivalencia entre expresiones regulares básicas y autómatas finitos
• Expresiónregular a*

Equivalencia entre expresiones regulares básicas y autómatas finitos
• Expresión regular a+

5

07/09/2010

Equivalencia entre expresiones regulares básicas y autómatas finitos
• Expresión regular a | b

Equivalencia entre expresiones regulares básicas y autómatas finitos
• Expresión regular (a|b)*

6

07/09/2010

Equivalencia entre expresiones regulares básicas yautómatas finitos
• Expresión regular (ac | b)*

Equivalencia entre expresiones regulares básicas y autómatas finitos
• Expresión regular (acd | b)*

7

07/09/2010

Ejercicios de autómatas con expresiones regulares
1. El lenguaje del autómata está formado por cualquier cadena de 1’s. La expresión regular del autómata es: 1* 2. El lenguaje del autómata está formado por todas las cadenasde a’s de longitud par. La expresión regular del autómata es: (aa)* 3. El lenguaje del autómata está formado por cadenas de cero ó más a’s seguidas de cero ó más b’s. La expresión regular del autómata es: a*b*

Resultados
1
1*
1

2
q0

a

(aa)*
q1

q0

a

3

a b q0

b a q1

a, b

q2

a*b*

8

07/09/2010

Lenguajes regulares
Expresión Regular Lenguaje RegularL={La cadena de 10} 10 1|0 1* (00)* 0*1* 1(1|0)* (1|0)*00 (1|0)*00(1|0)* L={Una cadena de 0 ó una cadena de 1} L={Cualquier cadena de 1’s incluyendo } L={Cadenas de 0’s de longitud par, incluyendo } L={Cadenas de ninguno o más 0’s concatenadas a cadenas de ninguno o más 1’s} L={Todas las cadenas sobre el alfabeto {1, 0} que empiecen con 1} L={Todas las cadenas sobre el alfabeto {1, 0} que terminenen 00} L={Cualquier combinación de 0’s ó 1’s que contengan al menos dos ceros consecutivos}

Ejercicios a resolver
• Encontrar las expresiones regulares correspondientes a:

a

a,b

b
q0 a

a,b

q0

q1

c
q0

a
b

q1 a
a b a, b

d
q0

b q1

a q2

9

07/09/2010

Ejercicios a resolver
• Describa los lenguajes de las siguientes expresiones regulares yrepresentar por medio de diagramas de transición los DFA’s que acepten las expresiones regulares :

Expresión regular Lenguaje regular
L={Cadenas sobre ={0, 1} que tienen por lo menos dos ceros}

L={Cadenas de longitud impar de 0’s}
L={Cadenas sobre subcadena 100} ={0, 1} que tienen la

L={Cadenas sobre terminen con 1}

={0, 1} que inicien y

Introducción Automátas Finitos
• Un analizadorléxico reconoce tokens, mediante un monitoreo de izquierda a derecha del programa fuente. Para hacer esta tarea menos difícil, utilizábamos las expresiones regulares para la especificación de los patrones o reglas que cumplen los tokens.

• Los autómatas finitos son las herramientas empleadas como reconocedores de tokens.

10

07/09/2010

• Un autómata finito es capaz de reconocer un conjuntoregular, es decir, un conjunto de cadenas denotado por cualquier expresión regular. • Recordemos que una expresión regular denota a un lenguaje regular. • Un autómata finito es un reconocedor para un lenguaje, su programación no es una tarea compleja, su entrada es una cadena x y responde “si” si x es una sentencia del lenguaje, “no” de otra manera.

11

07/09/2010

Clasificación
• Los...