Conceptos Fundamentales de Autómatas Finitos y Lenguajes Formales

Conceptos Fundamentales de Lenguajes y Autómatas

Equipo 1

1. ¿Qué es un autómata finito (AF)?

Es un modelo computacional que realiza cómputos de forma automática sobre una entrada para producir una salida.

2. ¿De qué otra manera se le puede llamar a un autómata finito?

También se le conoce como máquina de estado finito.

3. ¿Cuál es la finalidad de un autómata finito?

Su finalidad es reconocer lenguajes regulares, que corresponden a los lenguajes formales más simples según la Jerarquía de Chomsky.

4. ¿Cómo se clasifican los autómatas finitos?

Se clasifican en:

• Deterministas (AFD): Cada combinación de estado y símbolo de entrada produce un único estado siguiente.
• No Deterministas (AFND): Cada combinación de estado y símbolo de entrada puede producir uno o varios estados siguientes, o ninguno.

5. ¿Por qué elementos está conformado un AF?

Está conformado por un alfabeto, un conjunto de estados y un conjunto de transiciones entre dichos estados.

Equipo 2

1. ¿Qué es un autómata?

Son modelos matemáticos, representados a menudo como grafos dirigidos, que constan de al menos cinco elementos.

2. ¿Qué es un AFD?

Los Autómatas Finitos Deterministas (AFD) son aquellos en los que, para cada estado y cada símbolo del alfabeto, existe una y solo una transición definida.

3. ¿Qué es un AFND?

Los Autómatas Finitos No Deterministas (AFND) son aquellos en los que, para un estado y un símbolo de entrada, puede haber cero, una o varias transiciones posibles.

4. ¿Qué es un AFN-E?

Un AFN-E (o AFND con transiciones epsilon) es un tipo de AFND que permite transiciones sobre la cadena vacía, representada por el símbolo ε (épsilon).

5. ¿Qué es la conversión de un AFND a un AFD?

Es el procedimiento para transformar un Autómata Finito No Determinista (AFND) en un Autómata Finito Determinista (AFD) equivalente, facilitando su comprensión y su implementación en software.

Equipo 3

1. ¿Qué significa “AFND-V”?

Significa Autómata Finito No Determinista con Transiciones Vacías (equivalente a AFN-E).

2. ¿Qué algoritmo se utiliza comúnmente para construir un AFND a partir de una expresión regular?

Se utiliza el Algoritmo de Thompson.

3. ¿Qué operaciones o símbolos son fundamentales en el Algoritmo de Thompson?

Las operaciones fundamentales son la disyunción (unión), la concatenación y la clausura de Kleene (o iteración).

4. ¿Qué mecanismos son equivalentes para denotar los lenguajes regulares?

Los mecanismos equivalentes para denotar los lenguajes regulares son las Expresiones Regulares (ERs), los Autómatas Finitos Deterministas (AFDs) y los Autómatas Finitos No Deterministas (AFNDs).

5. ¿Cuál es la definición del Algoritmo de Thompson?

Es un algoritmo que permite construir un Autómata Finito No Determinista con Transiciones Vacías (AFND-V) a partir de una Expresión Regular (ER).

Equipo 4

1. ¿Qué es la minimización de estados en Autómatas Finitos?

Es el proceso de reducir el número de estados de un Autómata Finito (AF), fusionando estados equivalentes, sin alterar el lenguaje que reconoce.

2. ¿Qué implica la unión de estados equivalentes en la minimización de un AF?

Implica la unión de sus transiciones de entrada y salida, asegurando que el nuevo estado resultante mantenga el mismo comportamiento.

3. Si dos estados no son equivalentes en la minimización, ¿cómo se les denomina?

Se les denomina estados distinguibles.

4. ¿Cuándo se considera que dos estados son equivalentes?

Dos estados son equivalentes si, al unirlos en uno solo, el lenguaje aceptado por el autómata no se altera.

5. En la minimización de AF, ¿qué tipo de estados nunca serán equivalentes?

Un estado final nunca será equivalente a un estado no-final.

Equipo 5

1. ¿Qué elementos conforman la quíntupla de un autómata finito M=(Q, ∑, f, q0, F)?

La quíntupla de un autómata finito está conformada por:

• Q: Conjunto finito de estados.
• ∑ (Sigma): Alfabeto de entrada (conjunto finito de símbolos).
• f (o δ): Función de transición.
• q0: Estado inicial (un elemento de Q).
• F: Conjunto de estados finales (un subconjunto de Q).

2. ¿Qué letra representa el conjunto finito de estados?

R: Q

3. ¿Qué símbolo representa el conjunto finito de símbolos, también llamado alfabeto de entrada?

R: ∑ (Sigma)

4. ¿Qué elemento representa el estado inicial de un AF?

R: q0

5. ¿Cuál es el subconjunto de Q que representa el conjunto de estados finales?

R: F