Question

The Pumping Lemma for regular languages Let Σ={a,b}.

(a) Consider the languages L1={a,b,ab,aa,bb,aabb,aaa,bbb,aaabbb} and
L2=L(a∗∪b∗∪a∗b ∗)
Are L1 and L2 regular languages? If so, what is a valid pumping length for them?

(b) Consider the language L3={w∈Σ∗∣ the number a's is more than twice the number of b's }.
Prove that L3 is not a regular language.
(c) Consider a language L with the following property: L contains infinitely many words and for every natural number n, there exists a natural number m, such that L4 contains no words of lengths m+1,m+2,…m+n.
a)Provide an example of a language over Σ that has the above property.
b)Prove that a language with the above property is not regular.

Answer 1

L1 is a regular language with a valid pumping length of 1, and L2 is regular because it is composed of regular sub-languages. L3 is not a regular language as shown using the Pumping Lemma. L4 is an example of a language with the stated property and such languages cannot be regular as proven by contradiction using the Pumping Lemma.

Step-by-step explanation:

For part (a), L1 is a regular language because it is finite; any finite language is regular. A valid pumping length for L1 could be 1 since the language contains strings of length 1. The language L2 is also regular as it is defined over concatenation and Kleene star of regular languages Σ* and b*, which are both regular. A valid pumping length for L2 can be taken as the maximum length of strings required to go through all the states in the smallest automaton that recognizes L2.

For part (b), to prove that L3 is not a regular language, we can use the Pumping Lemma for regular languages. Assume that L3 is regular and let p be the pumping length. Consider the string s = a2pbp which is in L3. According to the Pumping Lemma, we should be able to split s into three parts, x, y, and z, such that for any i ≥ 0, the string xyiz belongs to L3. However, if we pump down (choose i = 0), the number of a's will no longer be more than twice the number of b's, and the resultant string will not be part of L3, contradicting the Pumping Lemma. Thus, L3 is not a regular language.

For part (c), an example of such a language is L4 = n ≥ 0, where for every natural number n, there's a corresponding gap of at least n in the lengths of strings that are in the language (since all strings in L4 have even length). To prove that a language with the property described is not regular, assume the contrary that there is such a regular language, L. According to the Pumping Lemma, there must be a pumping length, p, where any string s in L of length at least p can be divided into x, y, and z, with the string xyiz also in L for any i ≥ 0. However, this contradicts the property of L that there are consecutive lengths with no strings in L, thus proving such a language cannot be regular.