Question

Use Myhill-Nerode Theorem to prove the following languages are not regular

A1 = {0ⁿ1ⁿ2ⁿ| n >= 0}

A2 = {www| w E {a, b}*}

Answer 1

1.)Use Myhill-Nerode Theorem to prove the following languages are not regular

A1 = {0ⁿ1ⁿ2ⁿ| n >= 0}

Consider the sequence of strings x1, x2, . . . where x_i = 0ⁱ for i ≥ 1.

We now see that no two of these are equivalent to each other with respect to A1

Consider x_i = 0ⁱ and xj = 0^j for i is not equal to j.

Let z=1ⁱ and p=2ⁱ and notice that x_izp=0ⁱ1ⁱ2ⁱ  belongs to A1 but x_jzp=0^j1ⁱ2i does not belong to A1

Therefore no two of these strings are equivalent to each other and thus A1 cannot be regular.

One nice thing about this method for proving things nonregular is that, unlike the pumping lemma, it is always guaranteed to work because the corollary above is a precise characterization of the regular languages. The statement of this fact is known as the Myhill-Nerode Theorem after the two people who first proved it.

2.)Use Myhill-Nerode Theorem to prove the following languages are not regular

A2 = {www| w E {a, b}*}

(To use Myhill-Nerode Theorem,we need to find an infinite set of strings that are pairwise distinguishable relative to A2.

We know that any two distinct strings over the aphabet {a,b} are distinguishable.

So pick the set S={a,b}^*.

Notice that S is not the subset of A2.That's okay, we never said S needs to be subset of A2.)

Proof:

Let S = {a, b}*.

This set contains infinitely many strings. Now, consider any x, y belongs to S where x != y.

Then x≟x ∈ A2 and y≟x ∉ A2.

Consequently, x ≢A2y. Therefore, by the Myhill-Nerode theorem, EQ is not regular.