×

Search anything:

Pumping Lemma Questions

Learn Algorithms and become a National Programmer
Indian Technical Authorship Contest starts on 1st July 2023. Stay tuned.

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

Jonathan Buss

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

Read More

Vote for Author of this article: