Question: Problem 1 ( Pumping Lemma ) Use the pumping lemma to show that the following languages are not regular: L 1 = { 0 n

Problem 1(Pumping Lemma)
Use the pumping lemma to show that the following languages are not regular:
L1={0n1m:n>2m,m0}.
L2={10n10n:n0}.
L3={wwR:win{0,1}*} where wR denotes the reversal of w. For example (1000)R=0001.
Recall that the pumping lemma requires you to give a strategy for winning the following game:
The adversary chooses some integer p.
You choose a string winL such that |w|p.
The adversary chooses strings x,y,z such that w=xyz and |xy|p,|y|1.
You choose an integer i and you win if xyiz is not in L.
Therefore, for each language you ONLY need to answer the following questions (be concise):
What's your strategy for choosing the string w in the above game?
What's your strategy for choosing the integer i in the above game?
How do you know that xyiz is not in L?
Problem 1 ( Pumping Lemma ) Use the pumping lemma

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer
Step: 1 Unlock blur-text-image
Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock
Step: 3 Unlock

Students Have Also Explored These Related Programming Questions!