\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\Hom#1#2#3{\mathrm{Hom}_{#1}(#2, #3)} \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, 2003 \hspace*{0.4cm} CIS 511}}\\ \vspace{1cm} {\Large\bf Introduction to the Theory of Computation\\ \vspace{0.5cm} Homework 3}\\[10pt] February 20, 2003; Due March 18, beginning of class\\ \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 context-free, then $L^R$ is also context-free. \vspace {0.5cm} ``B problems'' must be turned in. \vspace {0.25cm}\noindent {\bf Problem B1 (50 pts).} An {\it $a$-transducer\/} (or {\it nondeterministic sequential transducer with accepting states\/}) is a sextuple $M = (K, \Sigma, \Delta, \lambda, q_0, F)$, where $K$ is a finite set of states, $\Sigma$ is a finite input alphabet, $\Delta$ is a finite output alphabet, $q_0\in K$ is the start (or initial) state, $F\subseteq K$ is the set of accepting (of final) states, and $$\lambda \subseteq K\times \Sigma^*\times \Delta^*\times K$$ is a finite set of quadruples called the {\it transition function\/} of $M$. \medskip An $a$-transducer defines a binary relation between $\Sigma^*$ and $\Delta^*$, or equivalently, a function $\mapdef{M}{\Sigma^*}{2^{\Delta^{*}}}$. We can explain what this function is by describing how an $a$-transducer makes a sequence of moves from configurations to configurations. The current configuration of an $a$-transducer is described by a triple $(p, u, v)\in K\times \Sigma^*\times \Delta^*$, where $p$ is the current state, $u$ is the remaining input, and $v$ is some ouput produced so far. We define the binary relation $\vdash_M$ on $K\times \Sigma^*\times \Delta^*$ as follows: For all $p, q\in K$, $u, \alpha\in\Sigma^*$, $\beta, v\in \Delta^*$, if $(p, u, v, q)\in \lambda$, then $$(p,\, u\alpha,\, \beta) \vdash_M (q,\, \alpha,\, \beta v).$$ Let $\vdash_M^*$ be the transitive and reflexive closure of $\vdash_M$. \medskip The function $\mapdef{M}{\Sigma^*}{2^{\Delta^{*}}}$ is defined such that for every $w\in \Sigma^*$, $$M(w) = \{y\in \Delta^*\ |\ (q_0,\, w,\, \epsilon) \vdash_M^* (f,\, \epsilon,\, y),\ f\in F\}.$$ For every language $L \subseteq \Sigma^*$, let $$M(L) = \bigcup_{w\in L} M(w).$$ \medskip (a) Let $\Sigma = \Delta = \{a, b\}$. Construct an $a$-transducer swapping $a$'s and $b$'s (for instance, if $w = abbaa$, then $y = baabb$). \medskip (b) Given an $a$-transducer $M = (K, \Sigma, \Delta, \lambda, q_0, F)$, define the new alphabet $T$ as follows: $$T = \{[p, u, v, q]\ |\ (p, u, v, q)\in \lambda\}.$$ Let $\mapdef{f}{T^*}{\Sigma^*}$ and $\mapdef{g}{T^*}{\Delta^*}$ be the homomorphisms defined such that $$f([p, u, v, q]) = u,\quad\hbox{and}\quad g([p, u, v, q]) = v.$$ \medskip Prove that the language $$\displaylignes{ R = \{[q_0, u_1, v_1, q_1][q_1, u_2, v_2, q_2]\cdots [q_{n-2}, u_{n-1}, v_{n-1}, q_{n-1}][q_{n-1}, u_n, v_n, q_n]\hfill\cr \hfill\ |\ [q_{i-1}, u_i, v_i, q_i]\in T,\, 1\leq i\leq n,\, q_n\in F,\, n\geq 1\}\cup \{\epsilon\ |\ q_0\in F\}\cr }$$ is a regular language. \medskip (c) Prove that $$\displaylignes{ f^{-1}(L)\cap R = \{[q_0, u_1, v_1, q_1][q_1, u_2, v_2, q_2]\cdots [q_{n-2}, u_{n-1}, v_{n-1}, q_{n-1}][q_{n-1}, u_n, v_n, q_n]\hfill\cr \hfill\ |\ [q_{i-1}, u_i, v_i, q_i]\in T,\, u_1u_2\cdots u_n\in L,\, q_n\in F,\, n\geq 1\}\cup \{\epsilon\ |\ q_0\in F,\, \epsilon\in L\}.\cr }$$ \medskip (d) Prove that $$M(L) = g(f^{-1}(L)\cap R).$$ \medskip If $\s{L}$ is a family of languages closed under intersection with regular languages, homomorphic images, and inverse homomorphic images, is $\s{L}$ closed under $a$-transductions? (Justify your answer). \medskip If $L$ is a regular language, is $M(L)$ regular? (Justify your answer). %\medskip %If $L$ is a context-free language, is $M(L)$ context-free? %(Justify your answer). \vspace{0.25cm}\noindent {\bf Problem B2 (80 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 (b) For simplicity of notation, drop the subscript $D$ in $\Delta_D$. Prove that there are only finitely matrices of the form $\Delta^{2^n}$. Use this fact to prove that for any regular language, $L$, the language \[ L_{2^n} = \{u\in \Sigma^* \mid (\exists v\in \Sigma^*) (|v| = 2^{|u|}\quad\hbox{and}\quad uv \in L)\} \] is also regular. Prove that the language \[ L_{2^{2^n}} = \{u\in \Sigma^* \mid (\exists v\in \Sigma^*) (|v| = 2^{2^{|u|}}\quad\hbox{and}\quad uv \in L)\} \] is also regular. \medskip In answering this question, you do not have to be very specific about the details of your construction. Sketch clearly your construction without worrying too much about its actual implementation. \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 finite-state control to encode transitions between pairs of boolean matrices of the form \[ (C, D) \longrightarrow (CD\Delta, D\Delta^2). \] Prove that \[ (I, I) \stackrel{n}{\longrightarrow} (\Delta^{n^2}, \Delta^{2n}). \] \medskip As in (b) you do not have to be very specific about the details of your construction. \medskip (d) Let $P(n)$ be any polynomial with integer coefficients, say \\ $P(n) = a_0n^d + a_1n^{d-1} + \cdots + a_d$. Denote the $i$th derivative of $P(n)$ by $P^{(i)}(n)$ (where $i\geq 0$, with $P^{(0)}(n) = P(n)$). Prove that \[ P(n+1) = \sum_{i = 0}^d \frac{P^{(i)}(n)}{i!}. \] \medskip\noindent {\it Hint\/}. Prove it for $P(n) = n^d$ and use linearity. \medskip Prove that \[ \frac{P^{(j)}(n + 1)}{j!} = \sum_{k = j}^d\binvec{k}{j} \frac{P^{(k)}(n)}{k!} \quad\hbox{and}\quad \frac{P^{(j)}(0)}{j!} = a_{d-j}. \] Use all this to 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\/}. Encode in the finite-state control transitions between $(d + 1)$-tuples of boolean matrices $(C_1, \ldots, C_n)$, where \[ (C_1, \ldots, C_n) \longrightarrow (D_1, \ldots, D_n) \quad\hbox{where}\quad D_j = \prod_{k = j}^d C_k^{\left({k \atop j}\right)}, \] with $0\leq j \leq d$. Then, \[ (\Delta^{a_{d-i}})_{i = 0}^d \stackrel{n}{\longrightarrow} (\Delta^{\frac{P^{(i)}(n)}{i!}})_{i = 0}^d \] and the first component on the righthand side is $\Delta^{P(n)}$. \medskip As in (b) and (c) you do not have to be very specific about the details of your construction. \vspace{0.25cm}\noindent {\bf Problem B3 (150 pts).} Review the definition of an ultimately periodic subset of $\natnums$ from Homework I, Problem B5. 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 B5, 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 B2 using B3(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. \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 B5). \vspace{0.25cm}\noindent {\bf Problem B4 (40 pts).} The purpose of this problem is to get a fast algorithm for testing state equivalence in a DFA. Let $D=(Q,\Sigma,\delta,q_{0},F)$ be a deterministic finite automaton. Recall that {\it state equivalence\/} is the equivalence relation $\equiv$ on $Q$, defined such that, $$p \equiv q\quad \hbox{iff}\quad \forall z\in\Sigma^* (\delta^{*}(p,z) \in F\quad \hbox{iff}\quad \delta^{*}(q,z) \in F).$$ and that {\it $i$-equivalence\/} is the equivalence relation $\equiv_{i}$ on $Q$, defined such that, $$p \equiv_{i} q\quad \hbox{iff}\quad \forall z\in\Sigma^*,\ |z| \leq i\ (\delta^{*}(p,z) \in F\quad \hbox{iff}\quad \delta^{*}(q,z) \in F).$$ \medskip A relation $S\subseteq Q\times Q$ is a {\it forward closure\/} iff it is an equivalence relation and whenever $(p, q)\in S$, then $(\delta(p, a), \delta(q, a))\in S$, for all $a\in\Sigma$. \medskip We say that a forward closure $S$ is {\it good\/} iff whenever $(p, q)\in S$, then $good(p, q)$, where $good(p, q)$ holds iff either both $p, q\in F$, or both $p, q\notin F$. \medskip Given any relation $R\subseteq Q\times Q$, recall that the smallest equivalence relation $R_\approx$ containing $R$ is the relation $(R \cup R^{-1})^*$ (where $R^{-1} = \{(q, p)\ |\ (p, q)\in R\}$, and $(R \cup R^{-1})^*$ is the reflexive and transitive closure of $(R \cup R^{-1})$). We define the sequence of relations $R_i\subseteq Q\times Q$ as follows: $$\eqaligneno{ R_0 &= R_{\approx}\cr R_{i + 1} &= (R_{i} \cup \{(\delta(p, a), \delta(q, a))\ |\ (p, q)\in R_i,\ a\in \Sigma\})_{\approx}. }$$ \medskip (i) Prove that $R_{i_{0}+1} = R_{i_{0}}$ for some least $i_0$. Prove that $R_{i_{0}}$ is the smallest forward closure containing $R$. \medskip We denote the smallest forward closure $R_{i_{0}}$ containing $R$ as $R^{\dagger}$, and call it the {\it forward closure of $R$\/}. \medskip (ii) Prove that $p\equiv q$ iff the forward closure $R^{\dagger}$ of the relation $R = \{(p, q)\}$ is good. \vspace{0.25cm}\noindent {\bf TOTAL: 320 points.} \end{document} \vspace {0.25cm} \noindent {\bf Problem B1 (40 pts).} Let $R$ be any regular language over some alphabet $\Sigma$. \medskip (1) Prove that the language $$L_1 = \{u\ |\ \exists v\in\Sigma^*,\, uv\in R,\, |v| = 2|u|\}$$ is regular. \medskip (2) Let $k\geq 1$ be any integer. Prove that the language $$L_1^k = \{u\ |\ \exists v\in\Sigma^*,\, uv\in R,\, |v| = k|u|\}$$ is regular.