## 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__