Step 1: Describe the language A1
A1 is the language of strings that consist of n zeros, followed by n ones, followed by n twos, with n greater than or equal to 0.
Step 2: Apply the pumping lemma
Let p be the pumping length. Choose a string w in A1 of the form \(w = 0^{p}1^{p}2^{p}\). It is clear that \(|w| \ge p\).
Step 3: Divide the string w into x, y, and z
According to the pumping lemma, we can divide w into three substrings x, y, and z such that:
1. \(w = xyz\)
2. \(|xy| \le p\)
3. \(|y| > 0\)
4. For all \(i \ge 0, xy^{i}z \in A_{1}\)
Step 4: Proof by contradiction
Since |xy| ≤ p, the substring y must consist of only zeros. Let \(y = 0^{k}\), where \(k > 0\).
Now, let's examine the string \(xy^{2}z\) which contains \((p + k)0s, p1s,\) and \(p2s\). Due to the extra k zeros, the string can't be in A1 since the numbers of 0s, 1s, and 2s should be equal. This contradicts condition (4) of the pumping lemma. Therefore, A1 is not a regular language.
#Language A2#
Step 1: Describe the language A2
Language A2 is the language of strings that consist of w concatenated three times, where w is any string of a's and b's.
Step 2: Apply the pumping lemma
Let p be the pumping length. Choose a string w in A2 of the form \(w = (a^{p}b^{p})^{3}\).
Step 3: Divide the string w into x, y, and z
According to the pumping lemma, we can divide w into three substrings x, y, and z such that:
1. \(w = xyz\)
2. \(|xy| \le p\)
3. \(|y| > 0\)
4. For all \(i \ge 0, xy^{i}z \in A_{2}\)
Step 4: Proof by contradiction
Since |xy| ≤ p, the substring y must consist of only a's. Let \(y = a^{k}\), where \(k > 0\).
Now, let's examine the string \(xy^{2}z\) which has an extra k a's in the first third of the string. This string cannot be of the form \(www\) any longer. Thus, this contradicts condition (4) of the pumping lemma. Therefore, A2 is not a regular language.
#Language A3#
Step 1: Describe the language A3
A3 is the language of strings that consist of \(2^{n}\) a's, where n is greater than or equal to 0.
Step 2: Apply the pumping lemma
Let p be the pumping length. Choose a string w in A3 of the form \(w = a^{2^{p}}\). This string is in A3 since \(2^{p} = 2^{n}\) for some n.
Step 3: Divide the string w into x, y, and z
According to the pumping lemma, we can divide w into three substrings x, y, and z such that:
1. \(w = xyz\)
2. \(|xy| \le p\)
3. \(|y| > 0\)
4. For all \(i \ge 0, xy^{i}z \in A_{3}\)
Step 4: Proof by contradiction
Since |xy| ≤ p, the substring y must consist of only a's. Let \(y = a^{k}\) where \(k > 0\). Now, let's examine the string \(xy^{2}z\) which has an extra k a's in it. The new length of the string is \(|xy^{2}z| = 2^{p} + k\). There is no integer n such that \(2^{p} + k = 2^{n}\), which means the string is not in A3. This contradicts condition (4) of the pumping lemma. Therefore, A3 is not a regular language.
Explanations 
Textbooks 
Exams 
Magazine 
