Pumping Lemma Questions

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 = {1ⁿ : n is a prime number} is a non-regular Language.

Problem 3

Let L be the language { 0ⁿ1ⁿ2ⁿ | 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 { aⁱb^jc^k | 0 <= i <= j <= k }. Show that this language is not a Context Free Language.

Problem 6

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

Problem 7

Prove that the language L = = {0^m1ⁿ : 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.