About the Final Exam
There will be eight problems on the final. Here are (a not necessarily exhaustive list of, but will be very similar to) the kinds of problems that you've seen so far and can expect may show up on the final.
- Anything that you did on the midterm.
- Given a language, describe its Myhill-Nerode equivalence classes.
- Given a language, construct a CFG/PDA that recognizes/matches it.
- Given a language operation, show that the context-free languages are closed under the operation.
- Given a language, show that it is not a context-free language.
- Given a language, is it a context-free language?
- Given a language, construct a Turing machine that recognizes/decides it.
- Given a modified Turing machine, show that an ordinary Turing machine can simulate it.
- Given a language operation, show that the recognizable/decidable languages are closed under the operation.
- Given a language, show that it is undecidable.
Exercises
- Give the Myhill-Nerode equivalence classes for the following languages.
- $\{w \mid \text{$w$ does not contain $aab$ as a subword} \}$
- $\{w \mid \text{$w$ contains $abab$ as a subword} \}$
- $\{w \mid \text{$w$ is not $aa$ or $bbb$} \}$
- $\{w \in \{a,b\}^* \mid |w|_a = |w|_b\}$
- $\{w \in \{(,)\}^* \mid \text{$w$ is balanced} \}$
- Construct a CFG/PDA for the following languages.
- $\{a^i b^j c^k \mid i \neq j \vee j \neq k \}$
- $\{a^i b^j \mid i = j \vee i = 2j \}$
- $\{w \in \{a,b\}^* \mid \forall x \in \{a,b\}^*, w \neq x^2 \}$
- $\{w \in \{(,),[,]\}^* \mid \text{$w$ is balanced} \}$
- $\{w \mid |w| = 4\}$
- Given a context-free language $L$, show that the following languages are context-free.
- $\{xay \mid xy \in L, a \in \Sigma \}$ (the language of words in $L$ with exactly one extra symbol inserted)
- $pref(L) = \{u \in \Sigma^* \mid ux \in L\}$
- $\{x_1 y x_2 \mid x_1 x_2 \in L, y \in L' \}$ (the language of words in $L$ with a word of $L'$ inserted, where $L'$ is context-free)
- $\{uv^R \mid u, v \in L \}$
- $cyc(L) = \{xy \mid \exists x,y \in \Sigma^*, yx \in L\}$
- Show that the following languages are not context-free.
- $\{a^{n^2} \mid n \in \mathbb N\}$
- $\{a^i b^j c^k \mid 0 \leq i \cdot j = k \}$
- $\{a^i b^j c^k \mid k = \max(i,j)\}$
- $\{w \in \{a,b,c\}^* \mid |w|_a = \min(|w|_b,|w|_c)\}$
- $\{uxv \mid ux \in L_1, xy \in L_2\}$ where $L_1, L_2$ are context-free languages
- Are the following languages context-free? Why or why not?
- $\{w \in \{a,b\}^* \mid |w|_a = |w|_b \}$
- $\{w^R \mid w \in L \}$, for a CFL $L$
- $\{ww^R w \mid w \in \Sigma^*\}$
- $\{a^i b^j \mid i = \lceil \log_2 j \rceil \}$
- $\{n_2(i) \# n_2(i+1) \mid \text{$n_2(k)$ is the binary representation of $k$} \}$
- Describe the operation of a Turing machine for each of the following languages.
- $\{0^n 1^n 0^n \mid n \geq 1\}$
- $\{w \in \{a,b\}^* \mid |w|_a \neq 2 |w|_b\}$
- $\{a^i b^j c^k \in \{a,b,c\}^* \mid i \cdot j \leq k \}$
- $\{a^i \mid \text{$i$ is prime} \}$
- $\{w \in \{0,1\}^* \mid \text{$w$ is a Fibonacci word} \}$ (def.)
- Show that each of the following languages is decidable.
- $\{w \in \Sigma^* \mid \forall u \in \Sigma^*, k \geq 2, w \neq u^k\}$
- $\overline L$, where $L$ is a decidable language
- $\{\langle G \rangle \mid \text{$G$ is a CFG and $G$ does not contain any useless symbols} \}$ (a symbol is useless if it is never used in any derivation or a string)
- $\{\langle M \rangle \mid \text{$M$ is a TM and $M$ does not move more than 500 tape cells from the beginning of the tape when run on $\varepsilon$}\}$ (think about the number of configurations)
- Anything from Question 6.
- Show that each of the following languages is recognizable.
- $\{\langle M,w \rangle \mid \text{$M$ is a TM and $M$ halts when run on $w$}\}$
- $\{\langle M \rangle \mid \text{$M$ is a TM and $M$ accepts a palindrome}\}$
- $\{\langle n \rangle \mid \text{$n \geq 2$ and $\exists p,q$ prime such that $n = p+q$} \}$
- $L_1 \cup L_2$, where $L_1$ and $L_2$ are recognizable.
- $L_1 \cap L_2$, where $L_1$ and $L_2$ are recognizable.
- Show that each of the following languages is undecidable. You can use Rice's theorem on some of these, but (1) "which ones are they?" is also a good exercise and (2) proving they're undecidable without it is also good practice.
- $\{\langle M \rangle \mid \text{$M$ is a TM and $M$ accepts a palindrome}\}$
- $\{\langle M \rangle \mid \text{$M$ is a TM and $L(M)$ is finite}\}$
- $\{\langle M \rangle \mid \text{$M$ is a TM and $M$ halts on all inputs}\}$
- $\{\langle M \rangle \mid \text{$M$ is a TM and $\varepsilon \in L(M)$}\}$
- $\{\langle G \rangle \mid \text{$G$ is a CFG and $L(G)$ is regular }\}$