CMSC 28000 — Problem Set 6

Instructions

This problem set is due on Wednesday February 26, 2020 at 18:00, to be submitted on Gradescope. Each problem is worth 10 marks in total.

Problems

1. Consider the language $L = \{w \in \Sigma^* \mid w = \theta(w)\}$, where $\Sigma = \{a,c,g,t\}$ and $\theta:\Sigma^* \to \Sigma^*$ is defined
   • if $w = \varepsilon$, then $\theta(w) = \varepsilon$,
   • if $w = b$ for $b \in \Sigma$, then $$\begin{matrix}\theta(a) = t & \theta(t) = a & \theta(c) = g & \theta(g) = c \end{matrix},$$
   • if $w = xb$ for $x \in \Sigma^*$ and $b \in \Sigma$, then $$\theta(xb) = \theta(b)\theta(x).$$
   Give a PDA that accepts $L$. Informally explain how the PDA is correct.
2. Suppose a language $L \subset \Sigma^*$ is accepted by a PDA $P$ by final state and $P$ has the property that for any word $w \in \Sigma^*$, the stack of $P$ never has more than 3 elements of $\Gamma$ on it. Prove that $L$ is regular.
3. Show that the language $L = \{a^i b^j c^k \mid i,j \geq 1, k = \min(i,j) \}$ is not context-free.