SSL 2K2 2026 -- UTN FRC CORDOBA --

Que es un automata con pila. Automata finito al que fue incorporado una memoria LIFO. Autómata finito al que se le ha incorporado una memoria FIFO (First In First Out). Autómata finito que utiliza una memoria de acceso aleatorio (RAM) para consultar cualquier símbolo de la cadena leída en cualquier orden. Máquina abstracta con memoria infinita diseñada específicamente para reconocer lenguajes dependientes del contexto (Tipo 1).

¿Para que sirve la memoria LIFO?. La memoria LIFO incrementa la capacidad de resolver problemas del automata finito convencional, al incoporarle la posibilidad de memorizar total o parcialmente la cadena leida y cualquier otra marca que ayuda al procesamiento de la misma. Permite al autómata acceder aleatoriamente a cualquier símbolo previamente leído de la cadena, eliminando la restricción de acceder únicamente al último elemento ingresado. Su función principal es convertir cualquier Autómata con Pila No Determinista en uno Determinista mediante el almacenamiento anticipado de todas las transiciones posibles. Sirve exclusivamente para almacenar los estados de aceptación del autómata, permitiendo que valide las cadenas regulares sin necesidad de leer la marca de fondo de pil.

Un automata con pila es una maquina abstracta por una septupla: AP = (Σ, Γ, Q, q₀, #, A, f). AP = (Σ, Γ, Q, q₀, δ, A, f). AP = (Σ, P, Q, q₀, #, A, f).

Que significa cada simbolo. Σ. Γ. Q. q0. #. A. f.

Indica el orden del funcionamiento. 1. 2. 3. 4. 5.

¿Porque es no determinista?. El AP puede leer un símbolo de entrada o no leer, por lo que puede realizar transiciones espontáneas (λ). El rango de la función de transición es P(Q × Γ*), por lo que puede transitar a varios estados y por cada estado:. Podría realizar sobre la pila una de varias acciones:. Porque la marca de fondo de pila (#) puede ser modificada aleatoriamente por la cadena de entrada en cualquier momento del proceso. Porque si la transición $f(q, \lambda, b)$ está definida para un estado, entonces obligatoriamente debe estar definida $f(q, a, b)$ para todo símbolo de entrada. (Al revés de la regla real de los APD).

¿Que funciones se pueden realizar sobre la píla?. Desapilar. Apilar. Cambiar.

¿Como un automata con píla se vuelve determinista?. Quitar las transiciones espontáneas y el conjunto potencia: f : Q × Σ × Γ → Q × Γ*. Permitir las transiciones espontáneas en forma restringida y quitar el conjunto potencia: f : Q × (Σ ∪ {λ}) × Γ → Q × Γ* con la condición de que si |f(q, λ, w)|=1 está definida no lo esté f(q, a, w) para ningún símbolo de entrada a. Permitir transiciones espontáneas ilimitadas siempre que el rango de la función de transición pertenezca al conjunto potencia: $f: Q \times \lambda \times \Gamma \rightarrow \mathcal{P}(Q \times \Gamma^*)$. Eliminando por completo el alfabeto de pila $\Gamma$ y la marca de fondo, haciendo que la función dependa únicamente de los estados y la entrada: $f: Q \times \Sigma \rightarrow Q$.

Vamos con un poco de simbologia. Configuración o Descripción Instantánea:. Configuración Inicial:. Configuración Final:. Movimiento:. Movimiento Generalizado:.

El arbol de configuraciones de una cadena , muestra adecuadamente el proceso que el AP realiza sobre la misma. Verdadero. Falso.

Para recordar... Davo. La cobra.

Te va sirviendo?. Se. No..

Para los automatas con pila, pueden definirse tres formas de aceptacion o reconocimineto de cadenas. Aceptacion por vaciado de pila. Reconocimiento por estado de aceptacion. Aceptacion por ambos criterios simultaneamente. Aceptación por cantidad finita de movimientos fijos definidos en la configuración inicia. Reconocimiento exclusivo por inversión del cabezal de lectura en autómatas con pila bidireccionales.

A que pertenece cada simbologia. Aceptacion por vaciado de pila. Aceptacion por estado de aceptacion. Aceptacion por ambos criterios simultaneamente.

A que pertenece cada simbologia de un lenguaje reconocido por un AP. Reconocimiento por vaciado de pila. Reconocimiento por estado de aceptacion. Reconocimiento por ambos criterios simultaneamente.

¿En qué consiste el problema del análisis sintáctico al relacionar un Autómata con Pila y una Gramática Independiente del Contexto (GIC)?. En determinar si una cadena α de símbolos terminales puede ser generada por la gramática a través de una derivación S →* α o un árbol de análisis sintáctico. En verificar de forma lineal que cada carácter de la cadena pertenezca al alfabeto de entrada ΣT, sin importar las reglas de producción ni el axioma. En transformar la gramática independiente del contexto en una gramática regular tipo 3 para que pueda ser procesada sin memoria de pila.

Cuales son las dos formas generales para construir un automata con pila, para que durante su funcionamiento al procesar una cadena de entrada, construya la derivacion o el arbol de analisis sintactico de la misma. Enfoque descendente. Enfoque ascendente. Enfoque lineal o léxico. Enfoque bidireccional.

¿Que hace cada una?. Enfoque descendente. Enfoque ascendente.

En relación con los compiladores, ¿en qué momento del proceso se emplean los Autómatas con Pila (AP)?. Se emplean en la primera etapa del compilador, llamada etapa de análisis (actuando como analizadores sintácticos). Se emplean en la segunda etapa del compilador, llamada etapa de síntesis, para llevar a cabo la generación y optimización del código intermedio. Se utilizan dentro de la etapa de análisis, pero actuando exclusivamente como analizadores léxicos para identificar los tokens del código.

¿Cuáles son los criterios principales por los que se distinguen las diferentes "familias" de analizadores sintácticos?. Por las formas normales de las producciones. El determinismo de los analizadores. La utilización de procedimientos recursivos. Por el aura.

Yendo a ASA Y ASD, te pregunto, ¿Que hace cada uno y como se lo denomina ?. Analizadores sintacticos descendentes. Analizadores sintacticos ascendentes.

A cual pertence este tipo de produccion. ASA. ASD.

A cual pertenece este ejemplo. ASA. ASD.

A cual pertenece este tipo de produccion. ASA. ASD.

A cual pertence este ejemplo de tipo de produccion. ASA. ASD.

En los algoritmos de análisis sintáctico con preanálisis, ¿qué características definen a los algoritmos LL(k) y LR(k). LL(k) realiza una lectura de izquierda a derecha con derivación por la izquierda (ASD), mientras que LR(k) realiza una lectura de izquierda a derecha con derivación por la derecha (ASA). En ambos, "k" es la cantidad de símbolos a preanalizar. LL(k) se usa para lenguajes lineales y LR(k) para lenguajes regulares, donde "k" indica el número máximo de elementos que puede almacenar la memoria LIFO. LL(k) genera el árbol sintáctico con un enfoque ascendente (ASA), mientras que LR(k) utiliza un enfoque descendente (ASD) partiendo desde el axioma.

¿Por qué el lenguaje L = {a^n b^n / n ≥ 1} NO puede ser reconocido por un Autómata Finito y requiere obligatoriamente un Autómata con Pila?. Porque un Autómata Finito requeriría infinitos estados para "contar" una cantidad n arbitraria de símbolos, mientras que el Autómata con Pila usa su memoria LIFO para apilar las a leídas y desapilarlas con cada b. Porque el Autómata Finito solo puede leer cadenas de longitud par, y este lenguaje incluye cadenas de longitud impar cuando n es un número primo. Porque la gramática que genera este lenguaje es de Tipo 3 (Regular) y los Autómatas Finitos solo reconocen lenguajes dependientes del contexto.

Al diseñar un Autómata con Pila (AP) para reconocer palíndromos, ¿cuál es la diferencia fundamental operativa entre procesar palíndromos de largo impar (ej: α * α^-1) y de largo par (ej: α α^-1)?. El palíndromo impar tiene un carácter central (*) que permite al AP saber exactamente cuándo empezar a desapilar, pudiendo ser Determinista (APD); en el par, el AP debe "adivinar" el centro usando No Determinismo (APND). El palíndromo par requiere vaciar la pila dos veces por cada símbolo leído, mientras que el impar solo necesita vaciar la pila al llegar al estado de aceptación. Los palíndromos de largo impar solo pueden ser reconocidos usando un enfoque Ascendente (ASA), mientras que los de largo par exigen exclusivamente un enfoque Descendente (ASD).

Ya terminaste, ahora disfruta del goat.. Agusneta. Benito SDR.