Clase 08: Autómatas finitos

Solicitado: Ejercicios 06: Autómatas finitos

1M. en C. Edgardo Adrián Franco Martínez

http://computacion.cs.cinvestav.mx/~efranco

@efranco_escom

edfrancom@ipn.mx

Contenido• Autómata finito

• Definición formal de autómata finito

• Configuración de un autómata finito

• Lenguaje reconocido por un autómata finito

• Ejemplos

• Ejemplo 1

• Ejemplo 2

• Ejemplo de programación en C

• Ejercicios 06: Autómatas finitos

2

Teo

ría

co

mp

uta

cio

na

l

Cla

se 0

8:

Au

tóm

ata

s fi

nit

os

Pro

f. E

dga

rdo

Ad

riá

n F

ran

co M

art

íne

z

Autómata finito• Un autómata finito es un modelo matemático de

una máquina que acepta cadenas de un lenguajedefinido sobre un alfabeto A.

• Consiste en un conjunto finito de estados y unconjunto de transiciones entre esos estados, quedependen de los símbolos de la cadena de entrada.

• El autómata finito acepta una cadena x si lasecuencia de transiciones correspondientes a lossímbolos de x conduce desde el estado inicial a unestado final. 3

Teo

ría

co

mp

uta

cio

na

l

Cla

se 0

8:

Au

tóm

ata

s fi

nit

os

Pro

f. E

dga

rdo

Ad

riá

n F

ran

co M

art

íne

z

• Los autómatas finitos reconocen los lenguajes

regulares, o de tipo 3 y se pueden representar

intuitivamente por una cinta y una cabeza de lectura.

•La cinta de entrada, sólo contiene

símbolos de un determinado

alfabeto, y se mueve en una sólo

dirección.

•El control de estados, determina el

funcionamiento del autómata.

•Una sentencia de un lenguaje

determinado, colocada en la cinta, y

leída por el autómata finito, es

reconocida por éste, si el control de

estados llega a un estado final.

4

Teo

ría

co

mp

uta

cio

na

l

Cla

se 0

8:

Au

tóm

ata

s fi

nit

os

Pro

f. E

dga

rdo

Ad

riá

n F

ran

co M

art

íne

z

Definición formal de autómata finito• Un autómata finito es una quíntupla A = ( E, Q, f, q0, F )

donde:

• E = {conjunto de entradas o vocabulario de entrada}

• E es un conjunto finito, y sus elementos se llaman entradas o símbolos

de entrada.

• Q = {conjunto de estados}

• Q es el conjunto finito de estados

• f: E*x Q→Q es la función de transición o función del estado siguiente

• Para un par del conjunto E × Q devuelve un estado perteneciente al conjunto Q,

y es el producto cartesiano de E por Q.

• q0 Є Q, es el estado inicial

• F ⊂ Q, es el conjunto de estados finales

5

Teo

ría

co

mp

uta

cio

na

l

Cla

se 0

8:

Au

tóm

ata

s fi

nit

os

Pro

f. E

dga

rdo

Ad

riá

n F

ran

co M

art

íne

z

Configuración de un autómata finito• Se entiende por configuración de un autómata

finito, a un par de la forma (q, W) donde q, es elestado actual, y W la cadena que queda por leer enese instante.

• La configuración inicial de un autómata finito es elpar (q0 , t) siendo t la sentencia o cadena de entradaa reconocer.

• La configuración final se representa por el par (qi , λ)donde qi Є F, y λ indica que no queda nada por entrar de lacinta.

6

Teo

ría

co

mp

uta

cio

na

l

Cla

se 0

8:

Au

tóm

ata

s fi

nit

os

Pro

f. E

dga

rdo

Ad

riá

n F

ran

co M

art

íne

z

• Un movimiento de un autómata finito, puede

definirse como el transito entre dos configuraciones,

y se representa por (q , aW) → (q', W) y se debe de

cumplir que f(q , a)=q'.

• Un autómata finito es una maquina de estados

capaz de reconocer un lenguaje regular. Si el

autómata es capaz de alcanzar en su configuración

final.

7

Teo

ría

co

mp

uta

cio

na

l

Cla

se 0

8:

Au

tóm

ata

s fi

nit

os

Pro

f. E

dga

rdo

Ad

riá

n F

ran

co M

art

íne

z

Lenguaje reconocido por un autómata finito

• Cuando un autómata transita a una configuración final

partiendo de la configuración inicial, en varios movimientos,

se dice que se ha producido aceptación o reconocimiento de

la cadena de entrada. Es decir que dicha cadena, pertenece al

lenguaje reconocido por el autómata.

• Por el contrario, cuando el autómata finito no es capaz de

llegar a un estado final, se dice que el autómata no reconoce

dicha cadena y que por tanto no pertenece al lenguaje.

8

Teo

ría

co

mp

uta

cio

na

l

Cla

se 0

8:

Au

tóm

ata

s fi

nit

os

Pro

f. E

dga

rdo

Ad

riá

n F

ran

co M

art

íne

z

• Para toda gramática regular "tipo 3", existe un autómata

finito "AF", tal que el lenguaje reconocido por el autómata

finito es igual al lenguaje generado por la gramática.

• La forma habitual de representar los autómatas finitos es

mediante un grafo o diagrama de estados, donde los nodos

son los estados y las ramas están marcadas con los símbolos

del alfabeto de entrada. Las ramas se construyen según la

función de transición, así debe de cumplir .

9

Teo

ría

co

mp

uta

cio

na

l

Cla

se 0

8:

Au

tóm

ata

s fi

nit

os

Pro

f. E

dga

rdo

Ad

riá

n F

ran

co M

art

íne

z

• Los nodos que representan los estados finales, suelen marcarse con

un doble círculo, y el estado inicial también se marca con una

flecha, encima de la cual se coloca la palabra INICIO.

10

Teo

ría

co

mp

uta

cio

na

l

Cla

se 0

8:

Au

tóm

ata

s fi

nit

os

Pro

f. E

dga

rdo

Ad

riá

n F

ran

co M

art

íne

z

abc*

Ejemplo 01

11

Teo

ría

co

mp

uta

cio

na

l

Cla

se 0

8:

Au

tóm

ata

s fi

nit

os

Pro

f. E

dga

rdo

Ad

riá

n F

ran

co M

art

íne

z

Ejemplo 01: Solución• Solución: Se construye el diagrama de estados, colocando en

primer lugar todos los estados dentro de círculos, marcando

con doble círculo el estado final. El estado inicial se indica con

una flecha que lo señala con la palabra INICIO encima. Para

construir las ramas, nos situamos en el primer estado de la

tabla de transiciones y se observa que f(q1,a)=q2, entonces se

traza una flecha entre q1 y q2, apuntando a q2, y se coloca

encima de la flecha el símbolo del vocabulario de entrada a.

De igual forma se recorre la tabla de transiciones para cada

estado y entrada completándose el diagrama de Moore.

12

Teo

ría

co

mp

uta

cio

na

l

Cla

se 0

8:

Au

tóm

ata

s fi

nit

os

Pro

f. E

dga

rdo

Ad

riá

n F

ran

co M

art

íne

z

Ejemplo 01: Lenguaje reconocido por un autómata finito

1313

Teo

ría

co

mp

uta

cio

na

l

Cla

se 0

8:

Au

tóm

ata

s fi

nit

os

Pro

f. E

dga

rdo

Ad

riá

n F

ran

co M

art

íne

z

Ejemplo 02

14

• Los identificadores de C son cadenas de letras, dígitos y guiones

bajos.

letra_ → [A-Za- z_] dígito → [0-9]id → letra_ ( letra_ | dígito)*

14

Teo

ría

co

mp

uta

cio

na

l

Cla

se 0

8:

Au

tóm

ata

s fi

nit

os

Pro

f. E

dga

rdo

Ad

riá

n F

ran

co M

art

íne

z

Ejemplo 02: Solución• Solución : Este ejemplo es inverso al anterior, pues se da un

lenguaje y se pide el autómata que lo reconoce. En primer

lugar se construye un diagrama de Moore, de tal forma que a

partir del estado inicial, después de leer una letra, acepte

letras o dígitos de forma variable, y cuando encuentre un

carácter diferente de letra o dígito alcance el estado final. El

diagrama de Moore es el que se muestra en la figura.

15

Teo

ría

co

mp

uta

cio

na

l

Cla

se 0

8:

Au

tóm

ata

s fi

nit

os

Pro

f. E

dga

rdo

Ad

riá

n F

ran

co M

art

íne

z

Ejemplo 02: Solución• $ representa a el fin de la cadena

• El autómata finito se deduce del diagrama de estaos y es el

siguiente:

• donde f se define por :

16

Teo

ría

co

mp

uta

cio

na

l

Cla

se 0

8:

Au

tóm

ata

s fi

nit

os

Pro

f. E

dga

rdo

Ad

riá

n F

ran

co M

art

íne

z

Ejemplo de programación en CPrograma que modela el AF=(E,Q,f,q0,F) donde:

E={a,b}, Q={q0, q1, q2, q3}, F={q1, q2}

f:ExQ->Q

f(q0,a)=q1

f(q0,b)=q3

f(q1,a)=q1

f(q1,b)=q2

f(q2,a)=q3

f(q2,b)=q2

f(q3,a)=q3

f(q3,b)=q317

Teo

ría

co

mp

uta

cio

na

l

Cla

se 0

8:

Au

tóm

ata

s fi

nit

os

Pro

f. E

dga

rdo

Ad

riá

n F

ran

co M

art

íne

z

AF que describe el lenguaje dado por la

expresión regular a+b*. "L(AF)=L(a+b*)"

//LIBRERIAS Y DEFINICIONES DE CONSTANTES#include <stdio.h >#define FIN_CADENA ' \ n'

//Modelado de los estadosenum{q0,q1,q2,q3};

//PROGRAMA PRINCIPALint main (void ){

int estado =q0; //Estado = Estado inicial q0char entrada ; // Caracter de entrada

entrada =getchar (); //Leer la primer entrada

//Ciclo que modela transicin del automata conforme avanza el cabezal de lecturawhile(entrada !=FIN_CADENA) //Mientras la entrada no sea el final de la cadena{

switch(estado ){

case q0: //Modelado de las transiciones del estado q0if(entrada =='a' ) estado =q1;else if(entrada =='b' )estado =q3;break;

case q1: //Modelado de las transiciones del estado q1if(entrada =='a' ) estado =q1;else if(entrada =='b' )estado =q2;break;

case q2: //Modelado de las transiciones del estado q2if(entrada =='a' ) estado =q3;else if(entrada =='b' )estado =q2;break;

case q3: //Modelado de las transiciones del estado q3if(entrada =='a' ) estado =q3;else if(entrada =='b' )estado =q3;break;

default:break;

}entrada =getchar (); //Leer de la segunda a más entradas

}

//Comprobar si al alcanzar la configuración final e l automata alcanzo un estado finalif(estado ==q1||estado ==q2) printf (" \ nCadena VALIDA en el lenguaje L( a+b*)" );else printf (" \ nCadena NO VALIDA en el lenguaje L( a+b*)" );

return 0; //Fin de programa}

18

Teo

ría

co

mp

uta

cio

na

l

Cla

se 0

8:

Au

tóm

ata

s fi

nit

os

Pro

f. E

dga

rdo

Ad

riá

n F

ran

co M

art

íne

z

Ejercicios 06: Autómatas finitos1. Diseñe autómatas finitos capaces de reconocer los siguientes

lenguajes definidos por la expresiones regulares:i. a+b*

ii. ab(cd)+e

iii. (a+b+)cd

iv. abz?b+

v. (cg)*gato+ |cd

2. Programe los autómatas finitos diseñados anteriormente yverifique su funcionamiento.

*Se entregarán antes del día Viernes 27 de Septiembre de 2013(23:59:59 hora limite)

*Sugerencia utilizar Jflap para el dibujo y simulación de los autómatas

*Incluir la redacción de cada ejercicio

*Portada y encabezados de pagina

*Incluir pantallazos del funcionamiento y pruebas19

Teo

ría

co

mp

uta

cio

na

l

Cla

se 0

8:

Au

tóm

ata

s fi

nit

os

Pro

f. E

dga

rdo

Ad

riá

n F

ran

co M

art

íne

z