Lab 7

Practice problems

Problems and topics listed here are for open discussion and practice. Feel free to work with a partner or ask the instructor questions. Towards the end of the lab period we may review some but not necessarily all answers. You are welcome to discuss solutions and strategies to these problems openly with classmates and the instructor outside of lab/class, on Piazza, and office hours.

Sample Problems

You do not need to submit any solutions to these problems. This work will not be graded.

  1. Sipser 4.3: Show that $\operatorname{\textit{ALL}}_{DFA}$ is decidable, where $\operatorname{\textit{ALL}}_{DFA}$ is defined as: \[ \operatorname{\textit{ALL}}_{DFA} = \{\langle A \rangle \ | \ \text{ is a } DFA \text{ and }L(A) = \Sigma^* \} \]
  2. Sipser 4.10: Show that $\operatorname{\textit{INFINITE}}_{DFA}$ is decidable, where $\operatorname{\textit{INFINITE}}_{DFA}$ is defined as: \[ \operatorname{\textit{INFINITE}}_{DFA} = \{\langle A \rangle \ | \ \text{ is a } DFA \text{ and }L(A) \text{ is an infinite language } \} \]
  3. Sipser 4.30: Let $A$ be an infinite Turing-recognizable language consisting of descriptions of Turing machines, $L(A) = \{\langle M_1 \rangle, \langle M_2 \rangle, \ldots\}$, where every $M_i$ is a decider. Prove that some decidable language $D$ is not decided by any decider $M_i$ whose description appears in $L(A)$. Hint: you may find it helpful to consider an enumerator for $A$.
  4. Sipser 5.1 Show that $\operatorname{\textit{EQ}}_{\operatorname{\textit{CFG}}}$ is undecidable. Theorem 5.13 shows $\operatorname{\textit{ALL}}_{\operatorname{\textit{CFG}}}$ is undecidable. You can use this result without proof. Guess that Automata Tutor update for Grammars isn't coming anytime soon.