Simulation of Pushdown Automata using Python

Simulation of Pushdown Automata using Python

Aditya Akangire, Abdul Mueed, Kartik Rupauliha, Sarthak Akkarbote, Ayush Vispute

Abstract— In the same approach that we create DFA for regular grammar, a pushdown automaton (PDA) is a technique for implementation of context- free grammar. Because of an extra memory segment called stack, a PDA can remember an immense amount of information, whereas a DFA can only remember a certain amount of information. In our project, we have implemented PDA using Python, and made simulations of four PDAs. To check if the input string has n number of 0s followed by n number of 1s, palindrome, if no. of 0s and 1s are equal or not and last one to check if, number of 1s are twice as compared to number of 0s. We also print transition tables for better understanding of PDA transitions and stack operations.

Keywords—python,pushdown automata, palindrome, automata theory, stack.