# Pushdown Automata for 0^N 1^N

Get FREE domain for 1st year and build your brand new site

In this article, we have presented a Pushdown Automata for the Language 0^{N} 1^{N}. Pushdown Automata can accept any Context Free Language.

Table of contents:

- Problem statement: 0
^{N}1^{N} - Pushdown Automata for 0
^{N}1^{N}

Pre-requisite: Pushdown Automata

Let us get started with Pushdown Automata for 0^{N} 1^{N}.

# Problem statement: 0^{N} 1^{N}

We will design a Pushdown Automata that will accept all strings of the Language L:

L: { 0^{N} 1^{N}: N >= 1}

This includes strings where N number of 0s are followed by N number of 1s.

Example strings:

- 00001111
- 01
- 0011
- 00000000001111111111

and much more.

# Pushdown Automata for 0^{N} 1^{N}

A Pushdown Automata is defined as a 5 tuple M = (Î£, Î“, Q, Î´, q) where:

- Î£ is the finite set of tape alphabet. Note this does not include blank symbol âœ·.
- Î“: is a finite set of stack alphabet and this includes the special symbol $.
- Q: is a finite set of states
- q is the start state and is a part of Q
- Î´ is the transition function. This is denoted as

The values are:

- Î£ = {0, 1}
- Î“ = {$, S}
- Q = {q
_{0}, q_{1}} where q_{0}is the start state.

The transition function Î´ consist of:

- q
_{0}0$ -> q_{0}R$S push S onto the stack - q
_{0}0S -> q_{0}RSS push S onto the stack - q
_{0}1$ -> q_{0}N$ first symbol in the input is 1; loop forever - q
_{0}1S -> q_{1}Re first 1 is encountered; e means empty. - q
_{0}âœ·$ -> q_{0}Ne input string is empty; accept - q
_{0}âœ·S -> q_{0}NS input only consists of 0s; loop forever - q
_{1}0$ -> q_{1}N$ 0 to the right of 1; loop forever - q
_{1}0S -> q_{1}NS 0 to the right of 1; loop forever - q
_{1}1$ -> q_{1}N$ too many 1s; loop forever - q
_{1}1S -> q_{1}Re pop top symbol from the stack - q
_{1}âœ·$ -> q_{1}Ne accept - q
_{1}âœ·S -> q_{1}NS too many 0s; loop forever

Consider this rule in the transition function:

q_{0}1S -> q_{1}Re

This means:

- the Pushdown Automata is in state q
_{0} - the tape head of Pushdown Automata reads the input symbol "1"
- the top symbol on the stack of Pushdown Automata is S

With this, the Pushdown Automata makes the following changes:

- The Pushdown Automata moves to state q
_{1} - the tape head of Pushdown Automata moves one cell to the right.
- the top symbol S on the stack is removed and no new symbol is inserted.

With this article at OpenGenus, you must have the complete idea of Pushdown Automata for the language 0^{N} 1^{N}.