Use Pumping Lemma to prove if a language is regular or not

Question

1. L3 = {𝜔𝜔ᴿ𝛽 | 𝜔, 𝛽 ∈ {0,1}⁺}
2. L4 = {1^1 0^j 1^k | 𝑖 > 𝑗 𝑎𝑛𝑑 𝑖 < 𝑘 𝑎𝑛𝑑 𝑖,𝑗, 𝑘 > 0}

Need step by step explanation.

Answer 1

Let me restate the Pumping Lemma because we will need terms from its statement.

If L is a regular language then there exists an integer p > 0 such that every string

w ∈ L of length at least p can be written as a concatenation of three strings w = xyz satisfying

|y| > 0

|xy| ≤ p

xyⁿz ∈ L for any n ≥ 0

1. L3 satisfies the Pumping Lemma, but it is not regular.

(Note that the Pumping Lemma has implication only in one direction;

it does not claim that any language satisfying its conditions is regular.)

Proof that L3 satisfies the Pumping Lemma with p = 2.

Pick any w of length at least 2.

Let a be its first symbol; that means w = av for some non-empty string v.

Decompose w = xyz, by setting

x is empty,

y = a

z = v

This choice satisfies the Pumping Lemma because any string, like

aaaav is in L with ω = a, β = aav.

2.

I assume that the statement contains a type. The definition is meant to be

L4 = {1ⁱ 0^j 1^k | 𝑖 > 𝑗 𝑎𝑛𝑑 𝑖 < 𝑘 𝑎𝑛𝑑 𝑖,𝑗, 𝑘 > 0}

Proof that L4 is not regular by the Pumping Lemma.

Assume that L4 is regular.

Then the Pumping Lemma gives us that number p.

Let w = 1^p+1 0 1^p+2

The string w is in L4 with i = p+1, j = 1, k = p+2.

Therefore we can write w = xyz, where xyz are strings satisfying the Pumping Lemma.

From |xy| ≤ p, we conclude that y must be a string of 1's; say it is a string of m 1's,

for some some integer m > 0.

Then xyyz is a string starting with p+1+m 1's, violating the condition i < k, which

all strings in L4 must satisfy.