Suggested languages for you:

Americas

Europe

Problem 15

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.

Expert verified

In brief, to show that the problem of determining whether a CFG generates all strings in \(1^*\) is decidable, follow these steps: (1) Check if the given CFG's language only contains 1's, (2) Convert it to Greibach Normal Form if needed, (3) Analyze its productions to ensure all combinations of 1's can be generated, (4) Confirm all non-terminals derive strings of 1's, and (5) Verify there are no useless non-terminal symbols. If these conditions are satisfied, the problem is decidable, and \(1^*\subseteq L(G)\).

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 4

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.

Chapter 4

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

Chapter 4

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.

Chapter 4

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

Chapter 4

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.

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