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

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

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 \(\\}\)

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.

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.

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.