Diferencia entre Pushdown Automata y Finite Automata

Autómatas Pushdown : 
Un autómata Pushdown (PDA) es una máquina de estado finito con un almacenamiento de pila adicional. Se utiliza una pila adicional para tomar la decisión de las transiciones además de los símbolos de entrada y el estado actual. Contiene las siguientes 7 tuplas: 

Autómatas finitos : 
un autómata finito es un modelo matemático de cualquier máquina mediante el cual podemos calcular la transición de estados en cada símbolo de entrada. Cada transición en los autómatas finitos depende de los símbolos de entrada y el estado de transición actual. Contiene las siguientes 5 tuplas: 

Veamos la diferencia entre Pushdown Automata y Finite Automata: 

S.NO autómatas pushdown autómatas finitos
1. Para la gramática de tipo 2 podemos diseñar autómatas pushdown. Para la gramática Tipo-3 podemos diseñar autómatas finitos.
2. Los autómatas pushdown no deterministas son más potentes que los autómatas pushdown deterministas. Los autómatas finitos no deterministas tienen los mismos poderes que los autómatas finitos deterministas.
3. No todos los autómatas pushdown no deterministas se transforman en sus autómatas pushdown deterministas equivalentes. Cada autómata finito no determinista se transforma en un autómata finito determinista equivalente
4. Los lenguajes libres de contexto pueden ser reconocidos por autómatas pushdown. Los lenguajes regulares pueden ser reconocidos por autómatas finitos.
5. Los autómatas pushdown tienen la pila adicional para almacenar secuencias largas de alfabetos. Finite Automata no tiene espacio para almacenar alfabetos de entrada.
6. Da la aceptación de los alfabetos de entrada al subir a la pila vacía y los estados finales. Acepta los alfabetos de entrada subiendo a estados finales.

Publicación traducida automáticamente

Artículo escrito por ashushrma378 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *