Suggested languages for you:

Americas

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.

What do you think about this solution?

We value your feedback to improve our textbook solutions.

- Access over 3 million high quality textbook solutions
- Access our popular flashcard, quiz, mock-exam and notes features
- Access our smart AI features to upgrade your learning

Chapter 1

Convert the following regular expressions to NFAs using the procedure given in Theorem 1.54. In all parts, \(\Sigma=\\{\mathrm{a}, \mathrm{b}\\}\). a. \(\mathrm{a}(\mathrm{abb})^{*} \cup \mathrm{b}\) b. \(a^{+} \cup(a b)^{+}\) c. \(\left(\mathrm{a} \cup \mathrm{b}^{+}\right) \mathrm{a}^{+} \mathrm{b}^{+}\)

Chapter 1

Consider the language $F=\left\\{\mathrm{a}^{i} \mathrm{~b}^{j} \mathrm{c}^{k} \mid i, j, k \geq 0\right.\( and if \)i=1\( then \)\left.j=k\right\\} .$ a. Show that \(F\) is not regular. b. Show that \(F\) acts like a regular language in the pumping lemma. In other words, give a pumping length \(p\) and demonstrate that \(F\) satisfies the three conditions of the pumping lemma for this value of \(p\). c. Explain why parts (a) and (b) do not contradict the pumping lemma.

Chapter 1

Let \(x\) and \(y\) be strings and let \(L\) be any language. We say that \(x\) and \(y\) are \(\operatorname{distin}\) guishable by \(L\) if some string \(z\) exists whereby exactly one of the strings \(x z\) and \(y z\) is a member of \(L\); otherwise, for every string \(z\), we have \(x z \in L\) whenever \(y z \in L\) and we say that \(x\) and \(y\) are indistinguishable by \(\boldsymbol{L}\). If \(x\) and \(y\) are indistinguishable by \(L\), we write \(x \equiv_{L} y\). Show that \(\equiv_{L}\) is an equivalence relation.

Chapter 1

Let \(\Sigma=\\{0,1,+,=\\}\) and \(A D D=\\{x=y+z \mid x, y, z\) are binary integers, and \(x\) is the sum of \(y\) and \(z\\} .\) Show that \(A D D\) is not regular.

Chapter 1

Let \(\Sigma=\\{0,1\\} .\) Let $W W_{k}=\left\\{w w \mid w \in \Sigma^{*}\right.\( and \)w\( is of length \)\left.k\right\\}$. a. Show that for each \(k\), no DFA can recognize \(W W_{k}\) with fewer than \(2^{k}\) states. b. Describe a much smaller NFA for \(\overline{W W}_{k}\), the complement of $W W_{k}$.

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