# Pushdown Automata for 0^N 1^N

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

1. Problem statement: 0N 1N
2. Pushdown Automata for 0N 1N

Pre-requisite: Pushdown Automata

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

# Problem statement: 0N 1N

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

L: { 0N 1N: 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 0N 1N

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 = {q0, q1} where q0 is the start state.

The transition function Î´ consist of:

• q00\$ -> q0R\$S push S onto the stack
• q00S -> q0RSS push S onto the stack
• q01\$ -> q0N\$ first symbol in the input is 1; loop forever
• q01S -> q1Re first 1 is encountered; e means empty.
• q0âœ·\$ -> q0Ne input string is empty; accept
• q0âœ·S -> q0NS input only consists of 0s; loop forever
• q10\$ -> q1N\$ 0 to the right of 1; loop forever
• q10S -> q1NS 0 to the right of 1; loop forever
• q11\$ -> q1N\$ too many 1s; loop forever
• q11S -> q1Re pop top symbol from the stack
• q1âœ·\$ -> q1Ne accept
• q1âœ·S -> q1NS too many 0s; loop forever

Consider this rule in the transition function:

q01S -> q1Re

This means:

• the Pushdown Automata is in state q0
• 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 q1
• 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 0N 1N.