Question

please provide steps as you solve the question.

>>>>>>>>>>>>>>>>>>>>>>>>>>>>

>>>>>>>>>>>>>>>>>>>>>>>>>>>

Prove that the following languages are not regular using the pumping lemma.

a. ? = {? ?? ?? ? | ?, ? ≥ ?}

b. ? = {? ∈ {?, #} ∗ | ? = ??#??# … #?? ??? ? ≥ ?, ?? ∈ ? ∗ ??? ????? ?, ??? ?? ≠ ?? ??? ????? ? ≠ ?

} Hint: choose a string ? ∈ ? that contains ? #’s.

Answer 1

a. We are given the language .

Let us assume that D is a regular language and let p be the pumping length of D. Suppose we choose a string w from D such that n>p for that string, then according to the pumping lemma we can break w in the following parts such that and

• 
• and
• 

Since n>p for w, the number of a's in w before the first b must be greater than p. From the third condition above, xy must be equal to and the y thus will also be made of a's. Now, if we pump y (like the first condition) into w, the number of a's before the first b will increase, keeping the number of a's following the last b constant. So, it will no longer be of the form . Hence, this is a contradiction and D is not a regular language.

b. We are given the language .

Let us assume that E is a regular language and let p be the pumping length of E. Suppose we choose a string w from E such that it contains p #'s then according to the pumping lemma we can break w in the following parts such that and

• 
• and
• 

Here, k will be equal to p+1. We will be having p+1 different number of 0's as 's. Hence the y part must contain more than one #.

If y contains more than one # it will be of the form where and .

If we pump y in w we will be having more than one but all members of E have .

So, this leads to a contradiction. Therefore, E is not a regular language.