
Introduction
Pushdown Automata is a finite automaton with additional memory known as a stack that aids in the recognition of Context-Free Languages. In this article, we discuss a type of Pushdown automata, i.e. Non-deterministic Pushdown Automata. We will also learn about its formal definition.
Also See, Simplification of CFG
Non-Deterministic Pushdown Automata
Non-deterministic Pushdown Automata (NPDAs) are similar to finite automata (FAs), but they contain a stack memory that can hold any amount of data.
(Source)
Stack in Non-Deterministic Pushdown Automata
The pop action reads the top symbol and removes it from the stack. The push operation pushes a designated symbol to the top of the stack. For example, push(X) means placing X on top of the stack, and the nop operation has no effect.
The stack symbols are distinct from the input tape's "language" alphabet.
Stack is used in the following manner:
- In the start state of the control automaton, there are only initial stack symbols on the stack.
- The state, input element, and top symbol in the stack determine the next step(transition) at each step.
Steps in Transition
The transition step includes the following:
- Make a state change (as FA).
- Reading a symbol from the input tape and shifting to the next symbol on the right (as FA).
- Modify the stack (add a symbol to the stack, remove a symbol from the stack, or leave the stack alone).
Transition functions formally define transition steps (often in the form of the transition instructions).
Check out this article - Converting NFA to DFA