1) This proof attempts to show that L = { 0ⁱ1^j | 0 < i < j } is not regular. The proof is flawed. Identify the reason that the proof is flawed.

Proof:

Assume that L is regular and let p=10 be the pumping length.

Let s = 0⁹1¹⁰.

s can be split into xyz, satisfying these conditions:

1. For each i0, xyⁱzL,

2. |y| > 0, and

3. |xy| p.

Assume s is split as follows: x = 0⁸, y = 0¹ and z = 1¹⁰.

Clearly, this satisfies conditions 2 and 3.

If we let i = 10, then xy¹⁰z = 0⁸0¹⁰1¹⁰= 0¹⁸1¹⁰.

xy¹⁰zL.

This contradicts condition 1, therefore L is not regular.

2) Fix the above proof to show L is not regular

3) This proof attempts to show that L = { 0ⁱ1^j | i > j >0 } is not regular.

The proof is flawed. Identify the reason that the proof is flawed.

Proof:

Assume that L is regular and let p=10 be the pumping length.

Let s = 0²⁰1¹⁰.

s can be split into xyz, satisfying these conditions:

1.For each i0, xyⁱzL,

2.|y| > 0, and

3.|xy| p.

In splits of s into xyz, y= 0⁺ because of condition 3

then xz has less zeros then s

and xzL.

This contradicts condition 1, therefore L is not regular.

4) Show that the language A is not regular.

A = {ww | w {0,1}*}

Another way to describe strings in A is that every string in A can be split in half where the first half is equal to the second half

Examples of strings in A are {00, 11, 0000,0101, 1010, 1111,1111, ....}