Volumen 3

Question 1

¿Cuales son los algoritmos para pasar del ER al AFD Mínimo?

Answer 1

Algoritmo de Thompson (ER a AFN)
Algoritmo de Clausura-ε (AFN a AFD)
Algoritmo de Clase (AFD a AFD Mínimo)

Question 2

¿Cuáles son las restricciones del Algoritmo de Thompson?

Answer 2

• Al estado inicial no le llegan transiciones.
• El estado final debe ser unico
• Del estado final no parten transiciones
• De cualquier estado no final pueden partir: una sola transición del alfabeto, una sola transicion epsilon, dos transiciones epsilon.

Question 3

¿Qué es el conjunto Clausura-ε?

Answer 3

Es el conjunto de estados formado por un estado, y todos aquellos estados a los cuales se llega utilizando solo transiciones-ε

Question 4

¿Qué es el conjunto Hacia?

Answer 4

Sea R un conjunto de estados:
Es el conjunto de estados a los cuales se transita con un determinado noterminal, desde los estados de R que tengan esa transición.

Question 5

¿Cómo se obtiene el complemento de un AFD?

Answer 5

Se obtiene invirtiendo los estados finales y no finales.
El AFD debe estar completo.

Question 6

¿Cómo es la intersección de dos AFDs?

Answer 6

Reconoce las palabras comunes a los LRs reconocidos por los dos AFDs.
Los estados son pares ordenados de estados, uno por cada AFD.

Question 7

¿Por qué es importante obtener el AFD mínimo?

Answer 7

1. Determinar si dos o más AFDs son equivalentes.
2. Probar la equivalencia de dos o más ERs.
3. El AFD mínimo tiene la TT mas reducida, hecho que beneficia a la implementación a la computadora.

Question 8

¿Cuándo dos AFD son equivalentes?

Answer 8

Si el AFD mínimo que se obtiene a partir de ellos es el mismo.

Question 9

¿Cuándo son ER son equivalentes?

Answer 9

Si son reconocidos por el mismo AFD mínimo.

Question 10

¿Cuándo son estados son equivalentes?

Answer 10

1. Pertenecen a la misma clase.
2. Tienen el mismo comportamiento.

Question 11

¿Qué es una Máquina de Turing?

Answer 11

Es un autómata determinístico con la capacidad de reconocer cualquier lenguaje formal.

Question 12

¿Por qué elementos está formada la Máquina de Turing?

Answer 12

1. Un alfabeto A de símbolos del lenguaje a reconocer.
2. Una cinta infinita dividida en secuencia de celdas.
3. Una cabeza de cinta.
4. Un alfabeto A’ de símbolos que pueden ser escritos en la cinta.
5. Un conjunto finito de estados que incluye un estado final, y un conjunto de estados finales.
6. Un programa, un conjunto de reglas que indican los pasos a realizar dado el estado de la MT y el caracter leído.