Using both Pumping Lemma and Equivalence class techniques pr

Using both Pumping Lemma and Equivalence class techniques prove that following languages are not regular

Using both Pumping Lemma and Equivalence class techniques prove that following languages are not regular A_1 = {0^n 1^n 2^n | n greaterthanorequalto 0} A_2 = {www|w belongs to {a, b}*} A_3 = {a^2n|n greaterthanorequalto 0} (here, a^2^n means a string of 2^n a\'s.)

Solution

b)A={www|w {a,b}*}

The case n = 0 just means that u = (so always matches r); and the case n = 1 just means that u matches r (so any string matching r also matches r). For example, if = {a, b, c} and r = ab, then the strings matching r are , ab, abab, ababab, etc. Note that we didn‘t include a regular expression for the ‘ occurring in the UNIX examples on Slide 1. However, once we know which alphabet we are referring to, = {a1, a2, . . . , an} say, we can get the effect of using the regular expression (a1|a2| . . . |an) which is indeed matched by any string in (because a1|a2| . . . |an is matched by any symbol in )

c)A={ a^2n|n>=0}

One way of showing L is not a regular language is: If L is regular then Lc(complement of L) is also regular.

Now assume if L is regular and M={Q, , delta, q0, F} denote the unique minimal state DFA for L.

Let p denotes the number associated by the Pumping Lemma with L.

We know that p=|Q|. Let G={a^(p^2)+i: i=1,2,….2p}.

We can think of the strings in G as being indexed by their length after subtracting the offset p^2. Using w to refer to the string a^(p^2)+i we have that |wi|+1= |wi+1|.

And therefore, our assumption is wrong and L is not a regular language.

a)A={0^n1^n2^n|n>=0}

Assume A is regular, with pumping length p

Let s be 0ⁿ1ⁿ2ⁿ

s cannot be divided into xyz because

And therefore, our assumption is wrong and L is not a regular language.

Thank you.