Lab 8

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. For each of the following languages, review if the language is decidable, Turing-recognizable, co-Turing-recognizable, or none of these. $A_{DFA}, A_{CFG}, A_{TM}, E_{DFA}, E_{CFG}, E_{TM}, EQ_{DFA}, EQ_{CFG}, EQ_{TM}$
  2. Using the formal definition of $O(\cdot)$, show $f(n)=2n+3$ is $O(n)$ by finding values $c$ and $n_0$ such that $f(n) \leq cn$ for all $n \geq n_0$.
  3. Show $P$ is closed under complement
  4. Show $P$ is closed under union