×

Search anything:

# Pumping Lemma Questions

#### Theory of Computation Get this book -> Problems on Array: For Interviews and Competitive Programming

In this article, we have presented some Questions which can be solving using Pumping Lemma in Theory of Computation. You must try these questions to test your understanding of Pumping Lemma before your examination.

To understand Pumping Lemma along with an example, go through this article which explains the concept clearly.

Following are a few problems which can be solved easily using Pumping Lemma. Try them.

## Problem 1

Check if the Language L = {w ∈ {0, 1}∗ : w is the binary representation of a prime number} is a regular or non-regular language.

## Problem 2

Prove that the Language L = {1n : n is a prime number} is a non-regular Language.

## Problem 3

Let L be the language { 0n1n2n | n >= 1 }. Show that language L is not a Context Free Language.

## Problem 4

Show that the Language L = { a n! : n >= 0} is not a Context Free Language.

## Problem 5

Let L be the language { aibjck | 0 <= i <= j <= k }. Show that this language is not a Context Free Language.

## Problem 6

Prove that the language L = = {0n1n : n >= 0} is not a regular language.

## Problem 7

Prove that the language L = = {0m1n : m > n >= 0} is not a regular language.

## Problem 8

Let L be the language {ww | w ∈ {0,1}* }. Show that language L is not a Regular Language.

## Problem 9

Let L be the language {ww | w ∈ {0,1}* }. Show that language L is not a Context Free Language.

With this article at OpenGenus, you must have complete knowledge of Pumping Lemma in Theory of Computation. #### Jonathan Buss

Associate Professor at University of Waterloo | BSc in Computing from California Institute of Technology, PhD from Massachusetts Institute of Technology (MIT)

Pumping Lemma Questions