Suggested languages for you:

Americas

Europe

Problem 23

Let \(B\) be any language over the alphabet \(\Sigma\). Prove that \(B=B^{+}\)iff $B B \subseteq B$.

Expert verified

In summary, to prove that a language B is equal to its concatenation closure, B^+, if and only if the concatenation of B with itself (BB) is a subset of B, we demonstrated two directions of the equivalence:
1. Assuming B = B^+, we showed that BB ⊆ B, as B^+ contains all concatenations of any length of words from B, including BB.
2. Assuming BB ⊆ B, we showed that B = B^+, because B ⊆ B^+ and B^+ ⊆ B (since B contains all elements from B^n where n goes from 1 to infinity).
Hence, we have proved the equivalence: B = B^+ ⟺ BB ⊆ B.

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

Prove that every NFA can be converted to an equivalent one that has a single accept state.

Chapter 1

Each of the following languages is the intersection of two simpler languages. In each part, construct DFAs for the simpler languages, then combine them using the construction discussed in footnote 3 (page 46) to give the state diagram of a DFA for the language given. In all parts, $\Sigma=\\{\mathrm{a}, \mathrm{b}\\} .$ a. \(\\{w \mid w\) has at least three a's and at least two b's \({ }^{\text {A }} \mathbf{b} .\\{w \mid w\) has exactly two a's and at least two b's \(\\}\) c. \(\\{w \mid w\) has an even number of a's and one or two b's \(\\}\) A. \(\\{w \mid w\) has an even number of a's and each a is followed by at least one b \(\\}\) e. \(\\{w \mid w\) starts with an a and has at most one b \(\\}\) f. \(\\{w \mid w\) has an odd number of a's and ends with a b \(\\}\) g. \(\\{w \mid w\) has even length and an odd number of a's \(\\}\)

Chapter 1

Prove that for each \(n>0\), a language \(B_{n}\) exists where a. \(B_{n}\) is recognizable by an NFA that has \(n\) states, and b. if \(B_{n}=A_{1} \cup \cdots \cup A_{k}\), for regular languages \(A_{i}\), then at least one of the \(A_{i}\) requires a DFA with exponentially many states.

Chapter 1

Let \(N\) be an NFA with \(k\) states that recognizes some language \(A\). a. Show that if \(A\) is nonempty, \(A\) contains some string of length at most \(k\). b. Show, by giving an example, that part (a) is not necessarily true if you replace both \(A\) 's by \(\bar{A}\). c. Show that if \(\bar{A}\) is nonempty, \(\bar{A}\) contains some string of length at most \(2^{k}\). d. Show that the bound given in part (c) is nearly tight; that is, for each \(k\), demonstrate an NFA recognizing a language \(A_{k}\) where \(\overline{A_{k}}\) is nonempty and where \(\overline{A_{k}}\) 's shortest member strings are of length exponential in \(k\). Come as close to the bound in (c) as you can.

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.

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