Automatas

REPUBLICA BOLIVARIANA DE VENEZUELA
MINISTERIO DE EDUACION Y DEPORTE
FACULTAD DE INGENIERIA
UNIVERSIDAD FERMIN TORO (CABUDARE)



AUTÓMATAS

MATERIA: METODOLOGIA DE LA INVESTIGACIÓN 1

SECCIÓN: SAIA A
INTEGRANTE:PEDRO GONZALEZ CI: 18102818
MIGUEL CAÑAMERO CI: 25627553
MATERIA: AUTÓMATAS
PROFESOR: EDECIO FREITEZ



CABUDARE; 07 DE JUNIO DE 2012
REFERENCIASBIBLIOGRÁFICAS
REFERENCIAS BIBLIOGRÁFICAS

* http://www.ia.urjc.es/grupo/docencia/automatas_itis/apuntes/capitulo5.pdf

* http://www.alipso.com/monografias/2561_automatas2/

* http://automatas-finitos.blogspot.com

* http://www.profesores.frc.utn.edu.ar/sistemas/ssl/marciszack/GHD/T-M-AFD.htm

* http://www.victorbravo.info/media/archivos/librotc.pdf

ACCESIBILIDAD ENTRE ESTADO:ACCESIBILIDAD ENTRE ESTADO:
DESARROLLO
DESARROLLO

Dados dos estados dentro de un autómata, se dice que uno de los estados es accesible desde el otro, si existe una palabra x formada por símbolos del alfabeto de entrada que hace que partiendo de este estado y a través de la aplicación de la función de transición se pueda llegar hasta el otro.

EJEMPLO:
De esta manera definiremos:
Sean p yq Q dos estados dentro de un AFD y
existe x W(∑) tal que:
f´( q , x ) = p Entonces se dice que:
pAq ( Se lee – p es accesible desde q )

• Dos estados p y q de un AFD son equivalentes si para toda cadena de
entrada w, δˆ( p, w) es un estado de aceptación si y sólo si δˆ( p, w) es
un estado de aceptación.

– En caso contrario, los estados serán distinguibles.

• Teorema: la equivalenciade estados es transitiva. Es decir, si para un
AFD dos estados p y q son equivalentes y q y r son equivalentes,
entonces p y r son equivalentes

• Teorema: si para cada estado q de un AFD se crea un bloque que
contiene a q y a todos los estados equivalentes a q, los bloques de
estados forman una partición del conjunto de estados.

– cada estado estará en un único bloque.

– todos losmiembros de un bloque son equivalentes.

– dos estados de bloques diferentes no pueden ser equivalentes.
AUTÓMATAS CONEXOS:
Es aquel en donde todos sus estados son accesibles desde el estado inicial. Por lo tanto un AFD será conexo si todo estado perteneciente al conjunto de estados es accesible desde el estado inicial.
Si en un AFD existieran estados que no son accesibles desde el estadoinicial, los mismos pueden ser eliminados, de manera de simplificar el autómata. Esta eliminación no afectará al comportamiento y por lo tanto continuará aceptando el mismo Lenguaje.
Ejemplo:
Dado el siguiente AFD definido como:
AFD1 = ( ∑, Q, qi, F, f ), donde:

∑= { 0,1 }
Q= { p, q, r , t, s }
qi = p
F= {q ,s }

Donde la función f será:
| F | 0 | 1 | También puede expresarse como:|
| <!--[if! vml]--><!--[endif]-->p | q | r | f(p, 0)= q f(p, 1)= r |
* | <!--[if ! vml]--><!--[endif]-->q | r | q | f(q, 0)= p f(q, 1)= q |
| R | r | r | f(r, 0)= r f(r, 1)= r |
| T | s | q | f(t, 0)= s f(t, 1)= q |
* | <!--[if ! vml]--><!--[endif]--> s | s | t | f(s, 0)= s f(s, 1)= t |

El Grafo correspondiente será:

Analizando, el grafodel AFD, vemos que a los estados t y s , es imposible acceder desde el estado inicial p, por lo tanto estos estados pueden ser eliminados del AFD y el comportamiento del autómata no se alterará.
equivalencia de afd:
Decimos que dos autómatas, M1 y M2, son equivalentes cuando aceptan el mismo lenguaje, es decir, L(M1) = L(M2). En este caso escribimos M1 » M2.

¿Cuándo dos autómatas no son...