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.

Table of contents:

  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.