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.
- Sipser 3.15: Show that the set of decidable languages is closed under union, concatenation, and intersection. For concatenation, try solutions with both a deterministic two-tape TM and a non-deterministic two-tape TM.
- Trace through the algorithm for parsing CNF grammars to show $aaabbb \in G$ where $G$ is given below.
\[
\begin{equation*}\begin{split}
S & \longrightarrow AB \ | \ CB \ | \ \varepsilon \\
C & \longrightarrow AS\\
A & \longrightarrow a \\
B & \longrightarrow b \\
\end{split}\end{equation*}
\]