Autómatas de Pila: Conceptos, Ejercicios y Pruebas Interactivas

Question 1

¿Cuál de las siguientes afirmaciones sobre autómatas de pila es incorrecta?

Accepted Answer

Son máquinas no deterministas.

Answer

Pueden reconocer lenguajes libres de contexto.

Answer

Utilizan una pila para almacenar símbolos.

Answer

Tienen un número finito de estados.

Question 2

¿Cuál es una característica principal de los Autómatas de Pila (PDA)?

Accepted Answer

Pueden reconocer lenguajes libres de contexto

Answer

Tienen un número finito de estados

Answer

No utilizan pilas para almacenar información

Answer

Son siempre deterministas

Question 3

¿Cuál es la definición correcta de un autómata de pila?

Accepted Answer

Una máquina abstracta capaz de reconocer lenguajes libres de contexto al utilizar una pila como memoria auxiliar.

Answer

Un autómata finito que puede apilar estados.

Answer

Una máquina que utiliza una cinta infinita como memoria.

Question 4

En un autómata de pila, ¿qué factores determinan la transición de un estado a otro?

Accepted Answer

El símbolo de entrada actual y el símbolo superior de la pila.

Answer

Solo el símbolo de entrada actual.

Answer

Solo el símbolo superior de la pila.

Question 5

¿Cuál es la estructura de datos esencial para implementar un autómata de pila?

Accepted Answer

Pila

Answer

Lista ligada

Answer

Array

Answer

Cola

Question 6

La forma normal de Chomsky para las gramáticas libres de contexto establece que:

Accepted Answer

Cada producción tiene la forma A → BC o A → a, donde A, B, C son símbolos no terminales y a es un símbolo terminal.

Answer

Cada producción tiene la forma A → aB, donde A es un símbolo no terminal y a, B son símbolos terminales.

Question 7

Una forma de mejorar la potencia de los autómatas de pila es mediante el uso de:

Accepted Answer

Pilas múltiples

Answer

Reglas de gramática adicionales

Answer

Automatas finitos anidados

Answer

Memorias finitas

Question 8

¿En qué aplicación práctica se utilizan comúnmente los autómatas de pila?

Accepted Answer

Análisis sintáctico en compiladores

Answer

Inteligencia artificial

Answer

Sistemas operativos

Answer

Bases de datos

Question 9

¿Qué tipo de lenguajes reconocen los autómatas de pila, según la jerarquía de Chomsky?

Accepted Answer

Lenguajes libres de contexto

Answer

Lenguajes regulares

Answer

Lenguajes recursivamente enumerables

Answer

Lenguajes no recursivos

Question 10

¿Cuál de las siguientes características es propia de los autómatas de pila?

Accepted Answer

Pueden reconocer cadenas que incluyen símbolos anidados.

Answer

Tienen un número limitado de estados.

Answer

Son incapaces de reconocer lenguajes no regulares.

Question 11

En un autómata de pila, el símbolo situado en la parte superior de la pila se conoce como:

Accepted Answer

Símbolo de cima

Answer

Símbolo de pila

Answer

Símbolo de fondo

Answer

Símbolo de entrada

Question 12

El teorema de Chomsky establece una correspondencia entre autómatas de pila y:

Accepted Answer

Gramáticas libres de contexto

Answer

Gramáticas regulares

Answer

Máquinas de Turing

Answer

Gramáticas recursivas

Question 13

¿Cuál es la principal diferencia entre un autómata de pila y un autómata finito?

Accepted Answer

Los autómatas de pila cuentan con una memoria adicional: la pila.

Answer

Los autómatas de pila son siempre más eficientes que los autómatas finitos.

Answer

Los autómatas de pila solo reconocen lenguajes regulares.

Question 14

En un diagrama de estados de un autómata de pila, ¿qué símbolo representa una pila vacía?

Accepted Answer

$

Answer

λ

Answer

#

Answer

0

Question 15

En un autómata de pila, ¿qué término describe la condición en la que se intenta desapilar una pila vacía?

Accepted Answer

Subdesbordamiento de pila

Answer

Superdesbordamiento de pila

Answer

Desbordamiento de pila

Question 16

En un autómata de pila, ¿qué tipo de estructura de datos se utiliza como pila?

Accepted Answer

Pila Last-In-First-Out (LIFO)

Answer

Pila ordenada

Answer

Pila First-In-First-Out (FIFO)

Answer

Pila binaria

Question 17

¿Cuál es la correspondencia entre los autómatas de pila y la jerarquía de Chomsky?

Accepted Answer

Los autómatas de pila reconocen los lenguajes de tipo 2 (libres de contexto) de la jerarquía de Chomsky

Answer

Los autómatas de pila son equivalentes a las gramáticas regulares (tipo 3) de Chomsky

Answer

El teorema de Chomsky no se aplica a los autómatas de pila

Question 18

En la notación de un estado de un autómata de pila, ¿qué simboliza el componente α?

Accepted Answer

El contenido de la pila

Answer

La transición a realizar

Answer

El símbolo de entrada actual

Answer

El estado actual

Question 19

¿Cuál es el propósito principal de utilizar una pila en un autómata de pila?

Accepted Answer

Proporcionar memoria adicional para almacenar información que ayuda a procesar lenguajes libres de contexto

Answer

Reducir el número de estados del autómata

Answer

Agilizar el proceso de lectura de la entrada

Question 20

¿Qué característica principal distingue a un autómata de pila no determinista de uno determinista?

Accepted Answer

Puede tener múltiples transiciones posibles para una misma entrada y estado actual

Answer

Solo puede procesar lenguajes regulares

Answer

Tiene un número ilimitado de estados

Question 21

¿Cuál de las siguientes afirmaciones describe con precisión la capacidad de los autómatas de pila?

Accepted Answer

Pueden reconocer y generar lenguajes libres de contexto.

Answer

Sólo pueden reconocer lenguajes regulares.

Answer

Sólo pueden generar lenguajes finitos.

Question 22

¿Cuál de los siguientes lenguajes NO puede ser reconocido por un autómata de pila?

Accepted Answer

{a^n b^m c^p | n, m, p ≥ 0, n + m ≠ p}

Answer

{a^n b^m | n ≥ m ≥ 0}

Answer

{a^n b^m c^m | n, m ≥ 0}

Answer

{a^n b^n c^n | n ≥ 0}

Question 23

¿Qué estructura de datos permite a los autómatas de pila recordar información durante su procesamiento?

Accepted Answer

Pila

Answer

Cola

Answer

Conjunto

Question 24

En una transición de empuje de un autómata de pila, ¿qué ocurre con la pila de salida?

Accepted Answer

Se añade un símbolo a la pila.

Answer

Se elimina un símbolo de la pila.

Answer

La pila permanece sin cambios.

Question 25

¿Cuál de los siguientes lenguajes es finito?

Accepted Answer

{a, b, c}

Answer

{a^n b^m | n, m ≥ 0}

Answer

{a^n b^n | n ≥ 0}

Answer

{a^n | n ≥ 0}

Question 26

¿Cuál de las siguientes propiedades caracteriza a las gramáticas libres de contexto?

Accepted Answer

Tienen una regla de producción inicial que no aparece en ningún lado derecho.

Answer

Siempre son ambiguas.

Answer

Sólo pueden generar lenguajes regulares.

Question 27

¿Cuál de los siguientes lenguajes NO es libre de contexto?

Accepted Answer

{a^n^2 | n ≥ 0}

Answer

{a^n b^m | n, m ≥ 0}

Answer

{a^n b^n | n ≥ 0}

Question 28

Los autómatas de pila son máquinas abstractas capaces de procesar:

Accepted Answer

Lenguajes libres de contexto.

Answer

Todos los lenguajes computables.

Answer

Exclusivamente lenguajes con gramáticas regulares.

Answer

Solo lenguajes regulares.

Question 29

De los siguientes lenguajes, ¿cuál NO puede ser reconocido por un autómata de pila?

Accepted Answer

{a^n b^m c^k | n, m, k ≥ 1}

Answer

{ww | w pertenece a {a, b}*}

Answer

{a^n b^n c^n | n ≥ 0}

Answer

{a^n b^n | n ≥ 0}

Question 30

¿Qué tipo de datos se almacenan en la pila de un autómata de pila?

Accepted Answer

Símbolos del alfabeto de la pila.

Answer

Números enteros.

Answer

Cadenas de entrada completas.

Answer

Valores booleanos.

Question 31

Una afirmación Falsa sobre los autómatas de pila es:

Accepted Answer

Pueden procesar todos los lenguajes computables.

Answer

Son más potentes que las máquinas de estados finitos.

Answer

Tienen memoria limitada.

Answer

Utilizan una pila para almacenar símbolos.

Question 32

En un autómata de pila, ¿para qué se utiliza la pila?

Accepted Answer

Para almacenar información sobre el estado actual y las transiciones realizadas.

Answer

Para almacenar la dirección de memoria del siguiente estado.

Answer

Para almacenar los símbolos de entrada del autómata.

Answer

Para almacenar la longitud de la cadena de entrada.

Question 33

Dada la gramática libre de contexto S → aSb | ε, ¿qué lenguaje reconoce un autómata de pila que la implementa?

Accepted Answer

L = {a^n b^n | n ≥ 0}

Answer

L = {a^n b^m | n, m ≥ 0}

Answer

L = {a^n b^(n+1) | n ≥ 0}

Answer

L = {a^n | n ≥ 0}

Question 34

Los autómatas de pila deterministas (PDA) reconocen:

Accepted Answer

Un subconjunto de los lenguajes libres de contexto.

Answer

Todos los lenguajes libres de contexto.

Answer

Solo lenguajes regulares.

Answer

Lenguajes con gramáticas ambiguas.

Question 35

¿Cuál de los siguientes es esencial para que un autómata de pila acepte un lenguaje correctamente?

Accepted Answer

Transiciones para vaciar la pila de forma controlada.

Answer

Un estado de inicio único.

Answer

Un estado de aceptación único.

Answer

Un alfabeto de entrada finito.

Question 36

Según el teorema de Chomsky, ¿qué tipo de autómata corresponde a los lenguajes libres de contexto?

Accepted Answer

Autómata de pila

Answer

Gramática formal

Answer

Máquina de Turing

Answer

Autómata finito

Question 37

Para reconocer el lenguaje L = {a^n b^n | n ≥ 0} con un autómata de pila, la pila debe:

Accepted Answer

Añadir un símbolo por cada 'a' leído y eliminar uno por cada 'b' leído.

Answer

Añadir un símbolo por cada 'a' y 'b' leído.

Answer

Eliminar un símbolo por cada 'a' y 'b' leído.

Answer

Mantener la pila vacía durante todo el proceso.

Question 38

¿Cuál de los siguientes lenguajes NO puede ser reconocido por un autómata de pila?

Accepted Answer

L = {a^n b^m c^n | n, m ≥ 0}

Answer

L = {a^n b^n | n ≥ 0}

Answer

L = {a^n b^m | n, m ≥ 0}

Answer

L = {w | w es una cadena palíndroma}

Question 39

¿Cuál de las siguientes aplicaciones es un ejemplo de la utilización práctica de los autómatas de pila?

Accepted Answer

Compiladores: Análisis sintáctico de código fuente.

Answer

Redes neuronales: Reconocimiento de patrones.

Answer

Máquinas virtuales: Ejecución de código.

Answer

Algoritmos de búsqueda: Exploración de grafos.

Question 40

¿Cuál de las siguientes afirmaciones sobre los autómatas de pila es verdadera?

Accepted Answer

Son máquinas abstractas que pueden procesar lenguajes libres de contexto.

Answer

Solo pueden procesar lenguajes regulares.

Answer

Son equivalentes a las máquinas de Turing.

Question 41

El siguiente lenguaje regular PUEDE ser reconocido por un autómata de pila:

Accepted Answer

a^n b^n

Answer

a^n b^m

Answer

a^n b^2n

Answer

a^n b^(n+1)

Question 42

¿Cuál de los siguientes es un componente esencial de un autómata de pila?

Accepted Answer

Pila

Answer

Contadores

Answer

Cinta

Question 43

¿Qué operación realiza un autómata de pila cuando lee el símbolo 'push(a)' en la entrada?

Accepted Answer

Empuja el símbolo 'a' en la pila.

Answer

Reemplaza el símbolo 'a' en la parte superior de la pila.

Answer

Saca el símbolo 'a' de la pila.

Answer

No realiza ninguna operación.

Question 44

Según el teorema de Chomsky, ¿qué tipo de gramática genera el lenguaje reconocido por un autómata de pila?

Accepted Answer

Gramática libre de contexto

Answer

Gramática de estructura de frase

Answer

Gramática sensible al contexto

Answer

Gramática regular

Question 45

El autómata de pila M tiene los siguientes estados: {q0, q1, q2}. El estado inicial es q0 y el estado de aceptación es q2. ¿Cuál de los siguientes es un estado inaccesible para M?

Accepted Answer

q3

Answer

q0

Answer

q1

Answer

q2

Question 46

¿Cuál de las siguientes operaciones es INVÁLIDA en un autómata de pila?

Accepted Answer

Sacar de una pila vacía

Answer

Reemplazar el símbolo superior de la pila

Answer

Empujar en una pila

Answer

Leer el símbolo superior de la pila

Question 47

Un autómata de pila no determinista (APND) acepta una cadena si:

Accepted Answer

Existe alguna secuencia de transiciones que conduce a un estado de aceptación.

Answer

Todas las secuencias de transiciones conducen a un estado de aceptación.

Answer

Ninguna secuencia de transiciones conduce a un estado de aceptación.

Question 48

El lenguaje {a^n b^n c^n | n ≥ 1} ES:

Accepted Answer

Libre de contexto

Answer

Regular

Answer

Sensible al contexto

Answer

Recursivo

Question 49

El autómata de pila M procesa la cadena 'ababa'. Si M se encuentra actualmente en el estado q0 y el símbolo superior de la pila es 'a', ¿cuál será el estado y el símbolo superior de la pila después de que M procese el siguiente símbolo 'b'?

Accepted Answer

q0, b

Answer

q1, b

Answer

q0, a

Answer

q1, a