Show that the problem of determining whether a CFG generates all strings in \(1^{*}\) is decidable. In other words, show that $\left\\{\langle G\rangle \mid G\right.\( is a CFG over \)\\{0,1\\}\( and \)\left.1^{*} \subseteq L(G)\right\\}$ is a decidable language.

Say that a variable \(A\) in CFL \(G\) is usable it it appears in some derivation of some string \(w \in G\). Given a \(\mathrm{CFG} G\) and a variable \(A\), consider the problem of testing whether \(A\) is usable. Formulate this problem as a language and show that it is decidable.

Let \(E=\\{\langle M\rangle \mid M\) is a DFA that accepts some string with more 1 s than \(0 s\\}\). Show that \(E\) is decidable. (Hint: Theorems about CFLs are helpful here.)

Let \(I N F I N I T E_{\mathrm{DFA}}=\\{\langle A\rangle \mid A\) is a DFA and \(L(A)\) is an infinite language \(\\} .\) Show that INFINITE DFA is decidable.

The following TM decides \(A\). "On input \(\langle M\rangle\) : 1\. Construct a DFA \(O\) that accepts every string containing an odd number of \(1 \mathrm{~s}\). 2\. Construct a DFA \(B\) such that \(L(B)=L(M) \cap L(O)\). 3\. Test whether \(L(B)=\emptyset\) using the \(E_{\mathrm{DFA}}\) decider \(T\) from Theorem 4.4. 4\. If \(T\) accepts, accept; if \(T\) rejects, reject."

The following TM \(I\) decides INFINITE \(_{\mathrm{DFA}}\). \(I={ }^{*} \mathrm{On}\) input \(\langle A\rangle\), where \(A\) is a DFA: 1\. Let \(k\) be the number of states of \(A\). 2\. Construct a DFA \(D\) that accepts all strings of length \(k\) or more. 3\. Construct a DFA \(M\) such that \(L(M)=L(A) \cap L(D)\). 4\. Test \(L(M)=\emptyset\) using the \(E_{\mathrm{DFA}}\) decider \(T\) from Theorem \(4.4\). 5\. If \(T\) accepts, reject; if \(T\) rejects, accept." This algorithm works because a DFA that accepts infinitely many strings must accept arbitrarily long strings. Therefore, this algorithm accepts such DFAs. Conversely, if the algorithm accepts a DFA, the DFA accepts some string of length \(k\) or more, where \(k\) is the number of states of the DFA. This string may be pumped in the manner of the pumping lemma for regular languages to obtain infinitely many accepted strings.