languajesy automatas examen

Introducción a la Teoría de Lenguajes Formales


1. Conteste las siguientes preguntas.

a) Menciones un mínimo de 3 ejemplos de autómatas

Automatas finitos deterministicos
Automatasfinitos no determinisicos
Automatas de pila

b) ¿Qué es la minimización de estados de un AFD?

Es cuando los estados de un AFD son distinguibles y alcanzables

c) Dibuje un AFDd) Mencione cuales son los pasos para pasar de ER a un AFND

Recononcer {λ}
Reconocer un simbolo{a} en ∑
Dadas las ER s y t
para s|t

para s●t
Dada la ER s, para s*



e) Dibuje unAFND








f) Mencione 3 características de un AFD

Para cada estado s y cada símbolo de entrada a, hayexactamente una arista etiquetada a que sale de s.

Un autómata finito deterministatiene una transición desde cada estado con cualquier entrada

Es un caso especial de un autómata finito no determinista

g) Mencione 3 características de un AFND


Conjunto de estadosdenotados como: estados S.
Un conjunto de símbolos de entrada S
Un conjunto de estados F considerados como estados de aceptación



h) Menciones los pasos para la conversión de un AFND a AFD

1.Calcular la función de transición

2. Para cada estado compuesto generado en el punto anterior, se calcula la función de transición

3. Se repite el paso 2 hasta que todos los estado compuestos hayansido definidos en la tabla

4. Se construye el AFD usando la tabla y etiquetando nuevamente todos los estados que aparecen en ella



i) ¿Cuál es el funcionamiento de un autómata?

Cuandocomienza el proceso de reconocimiento de una cadena de entrada el autómata se encuentra en el estado inicial y a medida que procesa cada simbolo de la cadena va cambiando el estado de acuerdo a lodeterminado por la función de transición , Cuando ya se ha procesado el ultimo de los simbolos de la cadena de entrada el automata se detiene en el estado final,Si el estado final en
el que se detuvo es un...