\documentclass[12pt]{article} \usepackage{amsfonts} %\documentstyle[12pt,amsfonts]{article} %\documentstyle{article} \setlength{\topmargin}{-.5in} \setlength{\oddsidemargin}{0 in} \setlength{\evensidemargin}{0 in} \setlength{\textwidth}{6.5truein} \setlength{\textheight}{8.5truein} %\input ../basicmath/basicmathmac.tex % %\input ../adgeomcs/lamacb.tex \input ../adgeomcs/mac.tex \input ../adgeomcs/mathmac.tex \def\fseq#1#2{(#1_{#2})_{#2\geq 1}} \def\fsseq#1#2#3{(#1_{#3(#2)})_{#2\geq 1}} \def\qleq{\sqsubseteq} % \begin{document} \begin{center} \fbox{{\Large\bf Spring, 2004 \hspace*{0.4cm} CIS 511}}\\ \vspace{1cm} {\Large\bf Introduction to the Theory of Computation\\ Jean Gallier \\ \vspace{0.5cm} Homework 3}\\[10pt] February 19, 2004; Due March 4, 2004\\ \end{center} ``A problems'' are for practice only, and should not be turned in. \vspace {0.25cm} \noindent {\bf Problem A1.} Prove that every finite language is regular. \vspace {0.25cm}\noindent {\bf Problem A2.} Sketch an algorithm for deciding whether two regular expressions $R, S$ are equivalent (i,e, whether $\s{L}[R] = \s{L}[S]$). \vspace {0.25cm}\noindent {\bf Problem A3.} Given any language $L\subseteq \Sigma^*$, let \[L^R = \{w^R \mid w \in L\},\] the {\it reversal language of $L$\/} (where $w^R$ denotes the reversal of the string $w$). Prove that if $L$ is regular, then $L^R$ is also regular. \vspace {0.5cm} ``B problems'' must be turned in. \vspace{0.25cm}\noindent {\bf Problem B1 (100 pts).} Let $D = (Q, \Sigma, \delta, q_0, F)$ be a DFA with $n$ states, say $q_1, \ldots, q_n$, where $q_1$ is the start state (Note, we denote the start state $q_1$, not $q_0$!) We associate with $D$ the $n\times n$ boolean matrix, $\Delta_D$, defined such that \[ \Delta_D(q_i, q_j) = \cases{ 1 & if $(\exists a\in \Sigma)(\delta(q_i, a) = q_j)$, \cr 0 & otherwise. \cr } \] Thus, $\Delta_D(q_i, q_j) = 1$ iff there is some edge from $q_i$ to $q_j$ (regardless of the label of that edge). Add and multiply matrices treating $\{0, 1\}$ as truth values, i.e. \begin{eqnarray*} 0 + 0 & = & 0\\ 0 + 1 & = & 1\\ 1 + 0 & = & 1\\ 1 + 1 & = & 1\\ 0 0 & = & 0\\ 0 1 & = & 0\\ 1 0 & = & 0\\ 1 1 & = & 1. \end{eqnarray*} (In other words, $\{0, 1\}$ is the two-element boolean ring). \medskip (a) Prove that $\Delta_D^k$ gives the $k$-step reachability relation on $D$, i.e., $\Delta_D^k(q_i, q_j) = 1$ iff $\delta^*(q_i, w) = q_j$, for some string $w\in \Sigma^*$ with $|w| = k$ (We set $\Delta_D^0 = I$, the identity matrix). Prove that there are only finitely many matrices $\Delta_D^k$, where $k \geq 0$. For any $k \geq 0$, let \[\Delta_D^{*[k]} = I + \Delta_D + \Delta_D^2 + \cdots + \Delta_D^k. \] Prove that there is a smallest $k\leq n - 1$ so that $\Delta_D^{*[k]} = \Delta_D^{*[k + i]}$ for all $i\geq 1$. Let $\Delta_D^* = \Delta_D^{*[k]}$, for the above $k$. Prove that $\Delta_D^*(q_i, q_j) = 1$ iff $\delta^*(q_i, w) = q_j$, for some string $w\in \Sigma^*$. \medskip For simplicity of notation, from now on drop the subscript $D$ in $\Delta_D$. \bigskip\noindent {\bf Warning\/}: Questions (b)--(d) must be solved directly {\it without\/} appealing to the results of problem B2. Either construct DFA's or NFA's (which is very hard!) or use Myhill-Nerode (my advice). \medskip (b) Prove that for any regular language, $L$, the languages \[ L_{2^n} = \{u\in \Sigma^* \mid (\exists v\in \Sigma^*) (|v| = 2^{|u|}\quad\hbox{and}\quad uv \in L)\} \] and \[ L_{2^{2^n}} = \{u\in \Sigma^* \mid (\exists v\in \Sigma^*) (|v| = 2^{2^{|u|}}\quad\hbox{and}\quad uv \in L)\} \] are also regular. \medskip\noindent {\it Hint\/}: Use the Myhill-Nerode theorem, i.e., find a suitable right-invariant equivalence relation of finite index. \medskip (c) %Observe that $\Delta^{(n+1)^2} = \Delta^{n^2}\Delta^{2n}\Delta$. Prove that for any regular language, $L$, the language \[ L_{n^2} = \{u\in \Sigma^* \mid (\exists v\in \Sigma^*) (|v| = |u|^2\quad\hbox{and}\quad uv \in L)\} \] is also regular. \medskip\noindent {\it Hint\/}. Use the Myhill-Nerode theorem. \medskip (d) Let $P(n)$ be any polynomial with integer coefficients, say \\ $P(n) = a_0n^d + a_1n^{d-1} + \cdots + a_d$. Prove that for every regular language, $L$, and any polynomial, $P(n)$, the language \[ L_P = \{u\in \Sigma^* \mid (\exists v\in \Sigma^*)(|v| = P(|u|) \quad\hbox{and}\quad uv \in L)\} \] is a regular language. \medskip\noindent {\it Hint\/}. Use the Myhill-Nerode theorem. %Prove it for $P(n) = n^d$ and use linearity. \vspace{0.25cm}\noindent {\bf Problem B2 (130 pts).} Review the definition of an ultimately periodic subset of $\natnums$ from Homework I, Problem B7. A function, $\mapdef{f}{\natnums}{\natnums}$ {\it preserves ultimate periodicity\/} iff $f^{-1}(U)$ is ultimately periodic whenever $U \subseteq \natnums$ is ultimately periodic. \medskip Given any language, $L \subseteq \Sigma^*$, let \begin{eqnarray*} L_f & = & \{u\in \Sigma^* \mid (\exists v\in \Sigma^*) (|v| = f(|u|)\quad\hbox{and}\quad uv \in L)\} \\ L'_f & = & \{u\in \Sigma^* \mid (\exists v\in \Sigma^*) (|v| = f(|u|)\quad\hbox{and}\quad v \in L)\}. \end{eqnarray*} \medskip (a) Assume that $L$ is a regular language. Prove that for any function, $\mapdef{f}{\natnums}{\natnums}$, if $f$ preserves ultimate periodicity then $L'_f$ is regular. \medskip (b) Prove that if $L'_f$ is regular whenever $L$ is regular, then $L_f$ is regular whenever $L$ is regular. Conclude that for any function, $\mapdef{f}{\natnums}{\natnums}$, if $f$ preserves ultimate periodicity then $L_f$ is regular. \medskip (c) Prove that if $L_f$ is regular whenever $L$ is regular, then $f$ preserves ultimate periodicity. \medskip Therefore, $L_f$ is regular whenever $L$ is regular iff $f$ preserves ultimate periodicity. \medskip (d) Checking that a function preserves ultimate periodicity is usually difficult. Hence, it is desirable to find more convenient criteria for the preservation of ultimate periodicity. Such a criterion is given below. \medskip For any two integers $m\geq 0$ and $p \geq 1$, let $[m]_p$ denote the set of integers congruent to $m$ modulo $p$, i.e., $[m]_p = \{n \in \natnums \mid n = p i + m,\, i\in \integs\}$. (Note: $\integs$ consists of the positive {\it and\/} negative integers, $\natnums$ of the {\it non-negative\/} integers.) Check quickly that Homework I, Problem B7, asserts that every ultimately periodic subset, $U$, of $\natnums$ can be written as \[U = F \oplus \bigcup_{i = 1}^k\> [m_i]_p,\] for some $p \geq 1$ and some pairwise distinct $m_i$'s, with $F$ a finite set disjoint from each of the $[m_i]_p$. Here $X \oplus Y = (X - Y) \cup (Y - X)$, the symmetric difference of $X$ and $Y$, i.e., $\oplus$ corresponds to {\it exclusive or\/}. Also, the set of ultimately periodic subsets of $\natnums$ is the smallest family containing all the finite sets and the sets $[m]_p$ and closed under union, intersection and complementation. Check that if $U$ and $V$ are two (infinite) ultimately periodic sets with periods $p_1$ and $p_2$, then $U\cup V$ is ultimately periodic with period $\mathrm{lcm}(p_1, p_2)$. \medskip We say that a function, $\mapdef{f}{\natnums}{\natnums}$, is {\it ultimately periodic modulo $m$\/} (with $m \geq 1$) iff there is some $p \geq 1$ and some $N \geq 0$ so that \[ f(n) \equiv f(n + p)\> (\mod\> m), \quad\hbox{for all $n \geq N$}. \] Prove that a function, $f$, is ultimately periodic modulo $m$ for all $m \geq 1$ iff $f^{-1}([i]_m)$ is ultimately periodic for all $i \geq 0$ and all $m\geq 1$. \medskip Assume that the function, $f$, is ultimately periodic modulo $m$ for all $m \geq 1$ and that $f^{-1}(\{n\})$ is ultimately periodic for every $n\in \natnums$. Then, prove that $f$ preserves ultimate periodicity. Prove that $f$ preserves ultimate periodicity iff \begin{enumerate} \item[(i)] The function, $f$, is ultimately periodic modulo $m$ for all $m \geq 1$, and \item[(ii)] The set $f^{-1}(\{n\})$ is ultimately periodic for every $n\in \natnums$. \end{enumerate} \remark Using the above, it is easy to show that the class of functions that preserve ultimate periodicity contains the functions, $n^k$, $k^n$ (for any fixed $k > 1$), and is closed under composition, addition, multiplication and exponentiation. \medskip (e) Reprove B1 using B2(b,d) (i.e., show that the languages $L_{2^n}$, $L_{2^{2^n}}$, $L_{n^2}$, $L_{P}$, are regular if $L$ is regular). \medskip (f) Prove that the function $f(n) = \log n$ does not preserve ultimate peridocity. Deduce that there are regular languages, $L$, for which \[ L_{\log n} = \{u\in \Sigma^* \mid (\exists v\in \Sigma^*) (|v| = \log(|u|)\quad\hbox{and}\quad uv \in L)\} \] is {\bf not\/} regular. \vspace {0.25cm}\noindent {\bf Problem B3 (50 pts).} Which of the following languages are regular? Justify each answer. \medskip (a) $L_{1}=\{ww \ |\ w\in \{a,b\}^{*}\}$ \medskip (b) $L_{2}=\{xy \ |\ x,y\in \{a,b\}^{*}\ \hbox{and}\ |x| = |y|\}$ \medskip (c) $L_{3}=\{a^{n}\ |\ n\ \hbox{is a prime number}\}$ \medskip (d) $L_{4} = \{a^mb^n\ |\ gcd(m, n) = 17\}$. \medskip (e) $L_5 = \{ww^R \mid w\in L\}$, where $L$ is some given regular language. \vspace{0.25cm}\noindent {\bf Problem B4 (60 pts).} Let $\Sigma$ be an alphabet. An equivalence relation on $\Sigma^*$ that is both left and right-invariant is called a {\it congruence\/}. Prove that a congruence satisfies the property: If $u \sim u'$ and $v \sim v'$, then $uv \sim u'v'$. Also recall that the reversal of a string, $w\in \Sigma^*$, is defined inductively as follows: \begin{eqnarray*} \epsilon^R & = & \epsilon\\ (ua)^R & = & a u^R, \end{eqnarray*} for all $u\in \Sigma^*$ and all $a\in \Sigma$. \medskip (i) Let $\sim$ be a congruence (on $\Sigma^*$) and assume that $\sim$ has $n$ equivalence classes. Define $\sim_R$ and $\approx$ by \[ u \sim_R v \quad\hbox{iff}\quad u^R \sim v^R, \quad\hbox{for all $u, v\in \Sigma^*$} \quad\hbox{and}\quad \approx\> =\> \sim \cap \sim_R. \] Prove that the relation $\approx$ is a congruence and that $\approx$ has at most $n^2$ equivalence classes. \medskip (ii) Given any regular language, $L$, over $\Sigma^*$ let \[ L^{(1/2)} = \{w\in \Sigma^* \mid ww^R \in L\}. \] Prove that $L^{(1/2)}$ is also regular using the relation $\approx$ of part (i). \medskip (iii) Let $L$ be any regular language over some alphabet $\Sigma$. For any natural number $k \geq 1$, let \[L^{(1/k)} = \{w \in \Sigma^* \mid (ww^R)^k \in L\} = \{w \in \Sigma^* \mid \underbrace{ww^Rww^R \cdots ww^R}_k \in L\}. \] Also define the languages \begin{eqnarray*} L^{1/\infty} & = & \{w \in \Sigma^* \mid (ww^R)^k \in L, \quad \hbox{for all $k\geq 1$}\}, \quad\hbox{and} \\ L^{\infty} & = &\{w \in \Sigma^* \mid (ww^R)^k \in L, \quad \hbox{for some $k\geq 1$}\}. \end{eqnarray*} Prove that there are only finitely many languages of the form $L^{(1/k)}$ and that they are all regular. Prove that $L^{1/\infty}$ and $L^{\infty}$ are regular. \vspace{0.5cm}\noindent {\bf TOTAL: 340 points.} \end{document} \medskip (g) ({\bf Extra Credit (40 pts).\/}) Prove again that if $L$ is regular and $f$ preserves ultimate periodicity, then $L_f$ is regular, using Myhill-Nerode as suggested below. \medskip If $L = L(D)$, for a trim DFA, $D$, the Myhill-Nerode equivalence relation $\simeq_D$ induces $n$ equivalence classes, $L_1, \ldots, L_n$, which are all regular. %Furthermore, since $\simeq_D\>\subseteq\> \rho_L$, %where $\rho_L$ is the Myhill-Nerode equivalence relation %associated with $L$, for any two strings %$u_1, u_2\in L_i$, we have %\[ %D_{u_1}(L) = D_{u_2}(L), %\] Prove that for each $L_i$, the language, $D_u(L) = \{v\in \Sigma^* \mid uv \in L\}$, where $u \in L_i$, does not depend on the choice of $u$. Thus, for each $L_i$, let $R_i = D_{u_i}(L)$, where $u_i$ is any string in $L_i$, for $i = 1, \ldots, n$. Since $\Sigma^* = L_1 \cup \cdots \cup L_n$, we can write \[L_f = (L_f\cap L_1) \cup \cdots \cup (L_f \cap L_n).\] To prove that $L_f$ is regular, it is enough to prove that each $L_f \cap L_i$ is regular. Show that \[ L_f\cap L_i = \{u \in L_i \mid (\exists v\in R_i) (|v| = f(|u|))\}, \] and finish up the proof (use Homework I, Problem B7).