\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, 2003 \hspace*{0.4cm} CIS 511}}\\ \vspace{1cm} {\Large\bf Introduction to the Theory of Computation\\ \vspace{0.5cm} Homework 1}\\[10pt] January 16, 2003; Due Febuary 4, beginning of class\\ \end{center} ``A problems'' are for practice only, and should not be turned in. \vspace {0.25cm} \noindent {\bf Problem A1.} Let $D = (Q,\Sigma,\delta,q_0,F)$ be a DFA. Recall that a state $p\in Q$ is {\it accessible\/} or {\it reachable\/} iff there is some string $w\in\Sigma^*$, such that $$\delta^{*}(q_0,w) = p,$$ i.e., there is some path from $q_0$ to $p$ in $D$. Consider the following method for computing the set $Q_{r}$ of reachable states (of $D$): define the sequence of sets $Q_{r}^{i}\subseteq Q$, where \medskip $Q_{r}^{0} = \{q_0\}$, \medskip $Q_{r}^{i+1} = \{q\in Q\ |\ \exists p\in Q_{r}^{i}, \exists a\in\Sigma,\ q = \delta(p,a)\}$. \medskip (i) Prove by induction on $i$ that $Q_{r}^{i}$ is the set of all states reachable from $q_0$ using paths of length $i$ (where $i$ counts the number of edges). \medskip Show that it is generally false that there is an index $i_{0}$, such that $Q_{r}^{i_{0}+1} = Q_{r}^{i_{0}}$, by giving a counter-example. \medskip (ii) Show that $Q_{r}^{i_{0}} = Q_{r}$ for some $i_0$ is generally false, by giving a counter-example. \medskip (iii) Change the inductive definition of $Q^i_r$ as follows: $$Q_{r}^{i+1} = Q^i_r\cup \{q\in Q\ |\ \exists p\in Q_{r}^{i}, \exists a\in\Sigma,\ q = \delta(p,a)\}.$$ Prove that there is a smallest integer $i_0$ such that $$Q_{r}^{i_{0}+1} = Q_{r}^{i_{0}} = Q_{r}.$$ Define the DFA $D_r$ as follows: $D_r = (Q_r,\Sigma,\delta_r,q_0,F\cap Q_r)$, where $\mapdef{\delta_r}{Q_r\times\Sigma}{Q_r}$ is the restriction of $\delta$ to $Q_r$. Explain why $D_r$ is indeed a DFA, and show that $L(D_r) = L(D)$. A DFA is said to be {\it reachable, or trim\/}, if $D = D_r$. \medskip\noindent {\bf Problem A2.} Given an alphabet $\Sigma$, for any language $L\subseteq \Sigma^*$, prove that $L^{**} = L^*$ and $L^*L^* = L^*$. \vspace {0.5cm}\noindent {\bf Problem A3.} Let $D = (Q,\Sigma,\delta,q_0,F)$ be a DFA. Prove that for all $p\in Q$ and all $u, v\in \Sigma^*$, \[ \delta^*(p, uv) = \delta^*(\delta^*(p, u), v). \] \vspace {1cm} ``B problems'' must be turned in. \vspace {0.25cm}\noindent {\bf Problem B1 (20 pts).} Let $L$ be any language over some alphabet $\Sigma$. \medskip (a) Prove that $L = L^+$ iff $LL \subseteq L$. \medskip (b) Prove that $(L =\emptyset$ or $L = L^*)$ iff $LL = L$. \vspace{0.25cm} \noindent {\bf Problem B2 (20 pts).} (a) Given the alphabet $\Sigma = \{0, 1, c\}$, construct a DFA accepting the following language: \[L = \{u_1cu_2c\cdots cu_{n-1}cu_n\ |\ n\geq 1,\, u_i \in \{00, 01, 10\}\}.\] \medskip (b) The strings in the above language can be interpreted as the coordinates of points in the plane as follows: Assume that you start with a square $S_0$, say of dimension $2\times 2$, divided into four equal subsquares. Then the lower left corner of each subsquare is referenced by one of the strings $00$, $01$, $10$, or $11$. A string $u_1cu_2c\cdots cu_{n-1}cu_n$ determines a point in the orginal square by proceeding recursively as follows: $u_1$ determines the subsquare $S_1$ whose lower left corner has coordinates $u_1$ in the original square; within the square $S_1$, $u_2$ determines the subsquare $S_2$ whose lower left corner has coordinates $u_2$; given the subsquare $S_i$ obtained at the end of step $i$, within this subsquare $S_i$, $u_{i+1}$ determines the subsquare $S_{i+1}$ whose lower left corner has coordinates $u_{i+1}$. The procedure stops with a point in the square $S_{n-1}$ obtained at stage $n-1$, the lower left corner of the subsquare $S_{n}$ whose coordinates with respect to $S_{n-1}$ are determined by $u_n$. \medskip Draw a rough picture by plotting a number of these points. What sort of shape do you get? \medskip {\it Remark\/}: The set of points defined above is a subset of the set of rational points of a fractal set known as the {\it Sierpinski gasket\/}. \vspace{0.25cm} \noindent {\bf Problem B3 (40 pts).} Given any two DFA's $D_1 = (Q_1, \Sigma, \delta_1, q_{0, 1}, F_1)$ and $D_2 = (Q_2, \Sigma$, $\delta_2, q_{0, 2}, F_2)$, a {\it morphism $\mapdef{h}{D_1}{D_2}$ of DFA's\/} is a function $\mapdef{h}{Q_1}{Q_2}$ satisfying the following two conditions: \begin{enumerate} \item[(1)] $h(\delta_1(p, a)) = \delta_2(h(p), a)$, for all $p\in Q_1$ and all $a\in \Sigma$; \item[(2)] $h(q_{0, 1}) = q_{0, 2}$. \end{enumerate} A {\it map $\mapdef{h}{D_1}{D_2}$ of DFA's\/} is a morphism satisfying the condition \begin{enumerate} \item[(3a)] $h(F_1) \subseteq F_2$. \end{enumerate} \medskip A {\it homomorphism $\mapdef{h}{D_1}{D_2}$ of DFA's\/} is a morphism satisfying the condition \begin{enumerate} \item[(3b)] $h^{-1}(F_2) \subseteq F_1$. \end{enumerate} \medskip A {\it proper homomorphism of DFA's\/} is a homomorphism of DFA's which is also a map of DFA's, i.e. it satisfies the condition \begin{enumerate} \item[(3c)] $h^{-1}(F_2) = F_1$. \end{enumerate} \medskip We say that a morphism, map, or homomorphism, $\mapdef{h}{D_1}{D_2}$ is {\it surjective\/} if $h(Q_1) = Q_2$. \medskip (a) If $\mapdef{h}{D_1}{D_2}$ is a morphism of DFA's, prove that $$h(\delta_1^*(p, w)) = \delta_2^*(h(p), w),$$ for all $p\in Q_1$ and all $w\in \Sigma^*$. \medskip As a consequence, prove the following facts: \medskip If $\mapdef{h}{D_1}{D_2}$ is a map of DFA's, then $L(D_1) \subseteq L(D_2)$. If $\mapdef{h}{D_1}{D_2}$ is a homomorphism of DFA's, then $L(D_2) \subseteq L(D_1)$. Finally, if $\mapdef{h}{D_1}{D_2}$ is a proper homomorphism of DFA's, then $L(D_1) = L(D_2)$. \medskip (b) Let $D_1$ and $D_2$ be DFA's and assume that there is a morphism $\mapdef{h}{D_1}{D_2}$. Prove that $h$ induces a unique surjective morphism $\mapdef{h_r}{(D_1)_r}{(D_2)_r}$ (where $(D_1)_r$ and $(D_2)_r$ are the trim DFA's defined in problem A1). This means that if $\mapdef{h}{D_1}{D_2}$ and $\mapdef{h'}{D_1}{D_2}$ are DFA morphisms, then $h(p) = h'(p)$ for all $p\in (D_1)_r$, and the restriction of $h$ to $(D_1)_r$ is surjective onto $(D_2)_r$. Moreover, if $L(D_1) = L(D_2)$, prove that $h$ induces a unique surjective proper homomorphism $\mapdef{h_r}{(D_1)_r}{(D_2)_r}$. \medskip (c) Relax the condition that a DFA morphism $\mapdef{h}{D_1}{D_2}$ maps $q_{0, 1}$ to $q_{0, 2}$ (so, it is possible that $h(q_{0, 1})\not= q_{0, 2}$), and call such a function a {\it weak morphism\/}. We have an obvious notion of {\it weak map\/}, {\it weak homomorphism\/} and {\it weak proper homomorphism\/} (by imposing condition (3a) or condition (3b), or (3c)). For any language, $L \subseteq \Sigma^*$ and any fixed string, $u\in \Sigma^*$, let $D_u(L)$, also denoted $L/u$ (called the {\it (left) derivative of $L$ by $u$\/}), be the language \[ D_u(L) = \{v\in \Sigma^*\mid uv \in L\}. \] Prove the following facts, {\bf assuming that $D_2$ is trim}: If $\mapdef{h}{D_1}{D_2}$ is a weak map of DFA's, then $L(D_1) \subseteq D_u(L(D_2))$, for some suitable $u\in\Sigma^*$. If $\mapdef{h}{D_1}{D_2}$ is a weak homomorphism of DFA's, then $D_u(L(D_2)) \subseteq L(D_1)$, for the same $u$ as above. Finally, if $\mapdef{h}{D_1}{D_2}$ is a weak proper homomorphism of DFA's, then $L(D_1) = D_u(L(D_2))$, for the same $u$ as above. \medskip Suppose there is a weak morphism $\mapdef{h}{D_1}{D_2}$. What can you say about the restriction of $h$ to $(D_1)_r$? What can you say about surjectivity ? (you may need to consider $(D_2)_r$ with respect to a {\bf different} start state). What happens (and what can you say) if $D_2$ is {\bf not} trim? \vspace {0.25cm}\noindent {\bf Problem B4 (50 pts).} (a) Given any two DFA's $D_1$ and $D_2$, prove that there is a DFA $D$ and two DFA maps $\mapdef{\pi_1}{D}{D_1}$ and $\mapdef{\pi_2}{D}{D_2}$ such that the following {\it universal mapping property of products\/} holds: For any DFA $M$ and any two DFA maps $\mapdef{f}{M}{D_1}$ and $\mapdef{g}{M}{D_2}$, there is a {\it unique\/} DFA map $\mapdef{h}{M}{D}$ such that \[f = \pi_1\circ h \quad\hbox{and}\quad g = \pi_2\circ h,\] as shown in the diagram below: \[\matrice{ & & D_1 \cr & \mapdiagul{f} & \mapupr{\pi_1} \cr M & \maprightu{h} & D \cr & \mapdiagdr{g} & \mapdownr{\pi_2} \cr & & D_2 \cr }\] Moreover, prove that $\pi_1$ and $\pi_2$ are surjective. Prove that $D$ is unique up to a unique DFA map isomorphism. This means that if $D'$ is another DFA and if there are two DFA maps $\mapdef{\pi_1'}{D'}{D_1}$ and $\mapdef{\pi_2'}{D'}{D_2}$ such that the universal mapping property of products holds, then there are two unique DFA maps $\mapdef{\varphi}{D}{D'}$ and $\mapdef{\varphi'}{D'}{D}$ so that $\varphi'\circ \varphi = \id_{D}$ and $\varphi\circ \varphi' = \id_{D'}$. What is the language accepted by $D$? \remark We call $D$ the {\it product of $D_1$ and $D_2$\/} and we denote it by $D_1\times D_2$. \medskip (b) Given any three DFA's $D_1$, $D_2$, and $D_3$ and any two DFA maps $\mapdef{f}{D_1}{D_3}$ and $\mapdef{g}{D_2}{D_3}$, prove that there is a DFA $D$ and two DFA maps $\mapdef{\pi_1}{D}{D_1}$ and $\mapdef{\pi_2}{D}{D_2}$ such that \[f\circ \pi_1 = g\circ \pi_2,\] as in the diagram below: \[ \matrice{ D & \maprightu{\pi_1} & D_1 \cr \mapdownl{\pi_2} & & \mapdownr{f}\cr D_2 & \maprightd{g}& D_3, \cr } \] \medskip\noindent and the following {\it universal mapping property of fibred products\/} holds: for any DFA $M$ and any two DFA maps $\mapdef{f'}{M}{D_1}$ and $\mapdef{g'}{M}{D_2}$ such that \[f\circ f' = g\circ g',\] as in the diagram below: \[ \matrice{ M & \maprightu{f'} & D_1 \cr \mapdownl{g'} & & \mapdownr{f}\cr D_2 & \maprightd{g}& D_3, \cr } \] \medskip\noindent there is a {\it unique\/} DFA map $\mapdef{h}{M}{D}$ such that \[f' = \pi_1\circ h \quad\hbox{and}\quad g' = \pi_2\circ h.\] Prove that $D$ is unique up to a unique DFA map isomorphism. This means that if $D'$ is another DFA and if there are two DFA maps $\mapdef{\pi_1'}{D'}{D_1}$ and $\mapdef{\pi_2'}{D'}{D_2}$ such that \[f\circ \pi_1' = g\circ \pi_2'\] and the universal mapping property of fibred products holds, then there are two unique DFA maps $\mapdef{\varphi}{D}{D'}$ and $\mapdef{\varphi'}{D'}{D}$ so that $\varphi'\circ \varphi = \id_{D}$ and $\varphi\circ \varphi' = \id_{D'}$. \remark We denote $D$ by $D_1\times_{D_3} D_2$ and call it a {\it fibred product of $D_1$ and $D_2$ over $D_3$\/}, or a {\it pullback of $D_1$ and $D_2$ over $D_3$\/}. \medskip Letting $T$ denote any one-state DFA accepting $\Sigma^*$ (this single state is final), observe that there is a unique DFA map from every DFA $D$ to $T$. Use this to show that if $D_1\times D_2$ is the product DFA arising in (a), then \[D_1\times D_2 = D_1\times_{T} D_2.\] \remark If we dualize (b), i.e., turn the arrows around, we get the notion of {\it fibred coproduct\/} or {\it pushout\/}. It can be shown that fibred coproducts exist, but this is a bit tricky. \vspace {0.25cm}\noindent {\bf Problem B5 (40 pts).} ({\it Ultimate periodicity\/}) A subset $U$ of the set $\natnums = \{0, 1, 2, 3,\ldots\}$ of natural numbers is {\it ultimately periodic\/} if there exist $m, p\in \natnums$, with $p \geq 1$, so that $n\in U$ iff $n + p\in U$, for all $n\geq m$. \medskip (i) Prove that $U\subseteq \natnums$ is ultimately periodic iff either $U$ is finite or there is a finite subset $F\subseteq \natnums$ and there are $k \leq p$ numbers $m_1, \ldots, m_k$, with $m_1 < m_2 < \cdots < m_k < m_1 + p$, and with $m_1$ the smallest element of $U$ so that for some $p \geq 1$, $n\in U$ iff $n + p\in U$, for all $n\geq m_1$, so that \[U = F \cup \bigcup_{i = 1}^k \,\{m_i + jp\mid j\in \natnums\}.\] \medskip Give an example of an ultimately periodic set $U$ such that $m$ and $p$ are not necessarily unique, i.e., $U$ is ultimately periodic with respect to $m_1, p_1$ and $m_2, p_2$, with $m_1\not= m_2$ and $p_1\not= p_2$. \remark A subset of $\natnums$ of the form $\{m + i p \mid i\in \natnums\}$ (allowing $p = 0$) is called a {\it linear set\/}, and a finite union of linear sets is called a {\it semilinear set\/}. Thus, (i) says that a set is ultimately periodic iff it is semilinear. \medskip (ii) Let $L\subseteq \{a\}^*$ be a language over the one-letter alphabet $\{a\}$. Prove that $L$ is a regular language iff the set $\{m \in \natnums \mid a^m\in L\}$ is ultimately periodic. Prove that the family of semilinear sets is closed under union, intersection and complementation (i.e., it is a boolean algebra). \medskip (iii) Let $L \subseteq \Sigma^*$ be a regular language over any alphabet $\Sigma$ (not necessarily consisting of a single letter). Prove that the set \[|L| = \{|w| \mid w \in L\}\] is ultimately periodic. \vspace {0.25cm}\noindent {\bf Problem B6 (90 pts).} ({\it wqo's\/}) We let $\natnums$ denote the set $\{0,1,2,\ldots\}$ of natural numbers, and $\natnums_{+}$ denote the set $\{1,2,\ldots\}$ of positive natural numbers. Given a set $S$, an {\it infinite sequence\/} is a function $s : {\bf N}_{+} \rightarrow S$. An infinite sequence $s$ is also denoted by $\fseq{s}{i}$, or by $\langle s_{1},s_{2},\ldots,s_{i},\ldots\rangle$. Given an infinite sequence $s=\fseq{s}{i}$, an {\it infinite subsequence\/} of $s$ is any infinite sequence $s'=\fseq{s'}{j}$ such that there is a strictly monotonic function $\mapdef{f}{\natnums_+}{\natnums_+}$ and $s'_{i}=s_{f(i)}$ for all $i>0$ (recall that a function $\mapdef{f}{\natnums_+}{\natnums_+}$ is {\it strictly monotonic\/} (or {\it increasing\/}) iff for all $i, j>0$, $ii$ such that $s_{i}\preceq s_{j}$. \medskip (b) Prove that the following statements are equivalent: \begin{enumerate} \item[(1)] $\preceq$ is a {\it wqo\/} on $A$. \medskip \item[(2)] Every infinite sequence $s=\fseq{s}{i}$ over $A$ contains some infinite subsequence $s'=\fsseq{s}{i}{f}$ such that $s_{f(i)}\preceq s_{f(i+1)}$ for all $i>0$. \end{enumerate} \medskip\noindent {\it Hint\/}. First, prove that if $\preceq$ is a wqo, then the number of terminal elements in any infinite sequence $s$ is finite. \medskip Given two preorders $\langle \preceq_{1},A_{1}\rangle$ and $\langle \preceq_{2},A_{2}\rangle$, the cartesian product $A_{1}\times A_{2}$ is equipped with the preorder $\preceq$ defined such that $(a_{1},a_{2})\preceq (a_{1}',a_{2}')$ iff $a_{1} \preceq_{1} a_{1}'$ and $a_{2} \preceq_{2} a_{2}'$. \medskip (c) Prove that if $\preceq_{1}$ and $\preceq_{2}$ are {\it wqo\/}, then $\preceq$ is a {\it wqo\/} on $A_{1}\times A_{2}$. \remark This is due to Nash-Williams. \medskip (d) Prove the following result. \medskip Let $n$ be any integer such that $n>1$. Given any infinite sequence $\fseq{s}{i}$ of $n$-tuples of natural numbers, there exist positive integers $i, j$ such that $i