×

Search anything:

Pumping Lemma Questions

Internship at OpenGenus

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.

Pumping Lemma Questions
Share this