About the Midterm
There will be four problems on the midterm. Here are the kinds of problems that you've seen so far and can expect may show up on the midterm.
- Prove something about words or languages by induction.
- Given a language, construct a DFA/NFA/regular expression that recognizes/matches it.
- Given a language operation, show that the regular languages are closed under the operation.
- Given a language, show that it is not a regular language.
- Given a language, is it a regular language?
Exercises
- Prove the following by induction.
- For all $x,y \in \Sigma^*$ and $q \in Q$,
$$\hat \delta(q,xy) = \hat \delta( \hat \delta(q,x),y)$$
for $\varepsilon$-NFAs (i.e. taking into account $\varepsilon$-closures).
- Given a regular expression $E$, show how to construct a regular expression $2E$ for the language
$$L(2E) = \{a_1 a_1 a_2 a_2 \cdots a_k a_k \mid a_1 a_2 \cdots a_k \in L(E)\}.$$
In other words, $2E$ doubles every symbol of a word matched by $E$.
- The Fibonacci words are defined recursively by
- $F_0 = 0$,
- $F_1 = 01$,
- $F_n = F_{n-1} F_{n-2}$.
For example, the first few Fibonacci words are
\begin{align*}
F_0 &= 0 \\
F_1 &= 01 \\
F_2 &= 010 \\
F_3 &= 01001 \\
F_4 &= 01001010 \\
F_5 &= 0100101001001 \\
F_6 &= 010010100100101001010
\end{align*}
Prove that for all $n \in \mathbb N$, $F_n$ does not contain the substring $11$ or $000$.
- Show that $\delta([\varepsilon],w) = [w]$ for all $w \in \Sigma^*$ in the Myhill-Nerode DFA $A_{\equiv_L}$.
- Construct a DFA/NFA/regular expression for the following languages over the alphabet $\{a,b\}$.
- $\{w \mid \text{$w$ contains $abab$ as a subword} \}$
- $\{w \mid \text{$w$ does not contain $aab$ as a subword} \}$
- $\{w \mid \text{$w$ is not $aa$ or $bbb$} \}$
- $\{cwc \mid c \in \Sigma, w \in \Sigma^*\}$
- $\{w \mid |w| = 4\}$
- $\overline{(b \overline \emptyset \cup \overline \emptyset a \cup \overline \emptyset aa \overline \emptyset \cup \overline \emptyset bb \overline \emptyset)}$ (you'll probably want to try to simplify this one first)
- Given a regular language $L \subseteq \{a,b\}^*$, show that the following languages are regular.
- $\frac 1 3 L = \{x \in \Sigma^* \mid \exists y \in \Sigma^*, xy \in L, |y| = 2|x|\}$
- $L' = \{xy \mid xay \in L\}$ ($L'$ is the language of words in $L$ with exactly one $a$ deleted.)
- $-L = \{x \in \Sigma^* \mid \exists u \in \Sigma^*, ux \in L\}$
- $\{x \in \Sigma^* \mid d_H(x,L) \leq k \}$.
Here, $d_H(x,L)$ is the Hamming distance from a word $x$ to a language $L$, defined by $d_H(x,L) = \min_{w \in L} d_H(x,w)$. The Hamming distance of two words of equal length is the number of positions in which they differ and is undefined if the two words are not of the same length. For example, $d_H(aabba,babaa) = 2$, since the two words differ in the first and fourth positions.
- $\{x \mid \text{$aaa,aba,abb,bba$ does not appear as a substring of $x$} \}$
- $L/L_1 = \{x \in \Sigma^* \mid \exists y \in L_1, xy \in L\}$ for a regular language $L_1 \subseteq \{a,b\}^*$
- Show that the following languages are not regular.
- $\{a^{2^n} \mid n \in \mathbb N\}$
- $\{a^i b^j \mid 0 \leq i \lt j\}$
- $\{a^i b^j c^k \mid 0 \leq i + j = k \}$
- $\{a^k y \mid y \in \{a,b\}^*, |y|_a \leq k, k \geq 1\}$
- $\{w \in \{a,b,c\}^* \mid |w|_a = \min(|w|_b,|w|_c)\}$
- $\{F_n \mid n \in \mathbb N\}$, the language of Fibonacci words.
- Are the following languages regular? Why or why not?
- $\{a^{2n} \mid n \in \mathbb N\}$
- $\{w \in \{a,b\}^* \mid |w|_a = |w|_b \}$
- $\{a^n x a^n \mid x \in \Sigma^*, n \in \mathbb N\}$
- $\{x c b^{|x|} \mid x \in \{a,b\}^* \}$
- $L^2$, for a regular language $L$
- $L^*$, where $L = \{a^p \mid \text{$p$ is prime}\}$