De acuerdo con la Jerarquía de Chomsky , el requisito de un cierto tipo de gramática para generar un idioma a menudo se enfrenta con una máquina adecuada que puede usarse para aceptar el mismo idioma. Cuando la gramática es simple, el lenguaje se vuelve más complejo, por lo que necesitamos una máquina más poderosa para entender el lenguaje y aceptarlo.
Ejemplo:
la gramática de tipo 0 es simple y genera un lenguaje recursivo enumerable (REL), que requiere una máquina poderosa como la » Máquina de Turing » para aceptar todas las strings.
Aquí discutimos sobre un escenario similar perteneciente a esta jerarquía, que es la Gramática Tipo 2; genera Lenguaje Libre de Control aceptado por un Autómata Push Down (PDA).
El diagrama de arriba muestra una cinta de entrada que es cómo funciona un autómata finito , las strings se aceptan en la cinta y el encabezado de lectura sigue actualizándose de acuerdo con las instrucciones proporcionadas por la unidad de control finita. Pushdown Automata, por otro lado, es una combinación de esta cinta y una estructura de datos Stack.
Las tuplas incluidas para formar un PDA son las siguientes:
Vemos que las primeras cuatro tuplas Q, 
, qo y F son similares como en el caso de un autómata finito.
Hablemos de 
, ahora que sabemos que Pushdown Automata tiene un mecanismo de pila para aceptar lenguajes que no son posibles en un Finite Automata. El problema surge cuando antes de una operación Push necesitamos verificar la Condición de desbordamiento, o antes de una Operación Pop, verificamos la Condición de subdesbordamiento.
Resolvemos este problema suponiendo que la pila es infinita, mientras que la condición vacía se supera introduciendo previamente un elemento en la pila antes de trabajar en la string.
Esta suposición nos ayuda de dos maneras: –
- Superamos la condición de subdesbordamiento, guardando así cualquier memoria para mantener un control sobre la pila vacía.
- El símbolo de pila inicial se puede utilizar para declarar que el procesamiento de strings se ha realizado correctamente.
El símbolo gamma ( 
) se utiliza para indicar todos los alfabetos de pila. Cada alfabeto de entrada (igual o diferente) se puede indicar con un símbolo de pila diferente. También es necesario ya que transporta el elemento superior de la pila a la máquina.
La función Delta ( 
) es la función de transición, cuyo uso se hará más claro al observar más de cerca las tres operaciones principales realizadas en Stack:-
- Empujar
- Estallido
- Saltar
1.PUSH
La operación de empuje se realiza como se muestra en el diagrama.
La transición tiene lugar en el siguiente orden: Entrada, elemento superior/lista final
Aquí, a es el elemento de entrada, que se inserta en la pila, lo que hace que el contenido final sea aZo.
2.POP
La operación Pop se realiza como se muestra en el diagrama.
La transición tiene lugar en el siguiente orden: – Elemento de entrada, Elemento superior/Confirmación de eliminación
Aquí, a es la entrada, c es el elemento que se eliminará y la confirmación de eliminación se muestra mediante el símbolo Epsilon que declara que el elemento inmediato se ha abierto y está vacío .
3. SALTAR
La operación de salto se realiza como se muestra en el diagrama.
La transición tiene lugar en el siguiente orden: Elemento de entrada, Elemento superior/Elemento superior
Aquí, a es la entrada y la pila permanece sin cambios después de esta operación.
Por lo tanto, esto concluye el estudio detallado sobre cómo funciona un Pushdown Automata. A continuación, nos dirigiremos a algunos ejemplos para que el trabajo y las transiciones sean más claros.
Publicación traducida automáticamente
Artículo escrito por AdityaPati y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA