 Suggested languages for you:

Europe

Problem 29

# Use the pumping lemma to show that the following languages are not regular. A. $$A_{1}=\left\\{0^{n} 1^{n} 2^{n} \mid n \geq 0\right\\}$$ b. $$A_{2}=\left\\{w w w \mid w \in\\{\mathrm{a}, \mathrm{b}\\}^{*}\right\\}$$ A c. $$A_{3}=\left\\{\mathrm{a}^{2^{n}} \mid n \geq 0\right\\}$$ (Here, $$\mathrm{a}^{2^{n}}$$ means a string of $$2^{n}$$ a's.)

Expert verified
Solution: A1: Using the pumping lemma, it is shown that adding extra zeros in the string breaks the condition where an equal number of 0s, 1s, and 2s is required. Hence, A1 is not a regular language. A2: By applying the pumping lemma, it is proven that adding extra a's in the first third of the string results in a contradiction, which means A2 is not a regular language. A3: Using the pumping lemma, it is shown that there exists no integer n such that the pumped string has a length equal to $$2^{n}$$, which contradicts the condition of A3. Hence, A3 is not a regular language.
See the step by step solution

## 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.

We value your feedback to improve our textbook solutions.

## Access millions of textbook solutions in one place

• Access over 3 million high quality textbook solutions
• Access our popular flashcard, quiz, mock-exam and notes features ## Join over 22 million students in learning with our Vaia App

The first learning app that truly has everything you need to ace your exams in one place.

• Flashcards & Quizzes
• AI Study Assistant
• Smart Note-Taking
• Mock-Exams
• Study Planner 