Bachiller En Ciencias Y Letras

UNIVERSIDAD MARIANO GALVEZ
COATEPEQUE

LENGUAJES FORMALES Y AUTOMATAS
Docente: LUIS ENRIQUE MENDOZA MUÑOZ

Tarea Automatas Equivalentes
* Definicion y ejemplos

CANDIDO DIONSIO RAMIREZRECINOS
906-10-12953

AUTÓMATAS EQUIVALENTES
Si dos Autómatas aceptan exactamente las mismas palabras, se dice que tales son equivalentes. El conjunto debe ser el mismo para ambos, mientras quepueden variar y la función necesariamente cambia entre ellos. Es evidente que siempre es mejor hacer el diseño más simple, ya que su implementación deberá ser más fácil y con menor riesgo de cometererrores al diseñarlo y sobre todo al implementarlo. Queda para el estudiante proponer algunos ejemplos de Autómatas equivalentes al resolver los problemas propuestos al final de este texto

Equivalencias* En la práctica, en muchos casos es más fácil definir un

* autómata no determinista que determinista

* Sin embargo, todo autómata finito determinista puede

* considerarsecomo un autómata finito no determinista,

* por lo que son equivalentes

* Para transformar un autómata no determinista a uno

* determinista, se pueden seguir una serie de sencillospasos

* La idea consiste en como se comprueba si una palabra es

* admitida por autómata no determinista

Ejemplo
1. Considere el siguiente autómata no determinista
2. B
A,B
SP
9
R
p
P
B,A
A
A,B
A,B
A
p
¿Qué lenguaje admite dicho autómata?

Ejemplo
* Notemos que en este ejemplo:
* En un solo paso, el autómata puede alcanzar los estados {q,r,s}
*En un segundo estado, puede alcanzar los estados {p,r,s}
* Notemos que lo que se tiene que hacer es:
* Se debe de ir construyendo la lista de estados a los que se
* puede acceder encada paso
* Para construir listas sucesivas, se parte en cada paso de la lista
* anterior y se unen las imágenes δ(p,σ), donde p es uno de los
* estados de la lista previa y σ es el...