Instructions
This problem set is due on Wednesday February 12, 2020 at 18:00, to be submitted on Gradescope. Each problem is worth 10 marks in total.
Problems
- Let $L = \{w \in \{a,b\}^* \mid w = w^R\}$, the language of palindromes over $\{a,b\}$. Show that every word in $\{a,b\}^*$ is in its own Myhill-Nerode equivalence class.
- Consider the regular expression $R = a^2 + (a^3)^*$.
- Give the transition diagram for an NFA equivalent to $R$. No proof is necessary. You do not need to follow any particular construction algorithm.
- Compute the derivatives for $R$ and use them to give the transition diagram for the minimal DFA equivalent to $R$.
- In Lecture 6, we discussed a DFA construction for the concatenation of two regular languages $L_m$ and $L_n$, recognized by DFAs with $m$ and $n$ states respectively, which resulted in a DFA of size at most $m2^n - 2^{n-1}$ states. However, if $L_m$ is a prefix-free regular language, then there is a much simpler construction using only at most $m+n-2$ states.
We say a language $L$ is prefix-free if for all $w = uv$ with $u,v \in \Sigma^+$, $w \in L \rightarrow u \not \in L$. In other words, if a word is in $L$, then no proper prefix of it is in $L$. It can be shown that a regular language is prefix-free if and only if its minimal DFA has a single final state with no outgoing transitions. Such a DFA is called non-exiting.
The easier construction is as follows: let $A_m$ and $A_n$ be the DFAs for $L_m$ and $L_n$. Merge the initial state of $A_n$ with the final state of $A_m$. As a result, we've removed two states, giving us our DFA of size $m+n-1$. (Note that the resulting language does not need to be prefix-free)
This works because our problem with arbitrary DFAs was that we didn't know if, when we encountered a final state, whether we should exit or not. As a result we had to guess all possible exits. With a prefix-free language, since no prefix of a word that's in the langauge can also be in the language, we don't need to guess; if we've reached the final state, then we know that we're finished with a word in $L_m$.
Show that for all $m, n \geq 3$, the upper bound on the number of states for this construction is tight by showing that a DFA for $L_m L_n$ requires $m+n-1$ states, where $L_m = L((a^{m-2})^*b)$ and $L_n = L((b^*+(a b^*)^n)^*)$.