Question

1) Use the Pumping Lemma to prove that the following languages are nonregular: i) L={a^ib^ja^i∣i,j>=0}

ii) L={a^ib^ja^jji,j>=0}
iii) L={a^ib^ja^jj∣i,j>=1}
iv) The language consisting of all words which can be broken into the same string repeated twice, e.g., abbabb or baabbbaabb
v) (a+b)^ia^i

Answer 1

Using the Pumping Lemma, we can prove that the given languages are nonregular, except for one of them. The languages that are nonregular violate the conditions of the Pumping Lemma by choosing a substring that can be pumped to generate strings not in the language. One of the languages is regular because it can be recognized by a finite automaton.

Step-by-step explanation:

To prove that the given languages are nonregular using the Pumping Lemma:

1. L = aibjai
   The language violates the conditions of the Pumping Lemma because we can choose a substring v such that pumping it up or down will result in a string that is not in the language. For example, if we choose v = ab, pumping it up gives us aabb which is not in the language.
2. L = aibjaji
   Similarly, this language also violates the conditions of the Pumping Lemma. If we choose v = abba, pumping it up gives us abbaa which is not in the language.
3. L = i, j ≥ 1
   In this case, if we choose v = abba, pumping it up gives us abbabbaa which is not in the language.
4. L = w
   This language is nonregular because it cannot be recognized by a finite automaton. The automaton would need to remember the first part of the string in order to check if the second part matches it, which is not possible.
5. L = {(a+b)iai}
   This language can be recognized by a finite automaton, therefore it is regular.