\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 2}\\[10pt] February 3, 2004; Due February 19, 2004\\ \end{center} ``A problems'' are for practice only, and should not be turned in. \medskip\noindent {\bf Problem A1.} Recall that two regular expressions $R$ and $S$ are equivalent, denoted as $R \cong S$, iff they denote the same regular language ${\cal L}[R] = {\cal L}[S]$. Show that the following identities hold for regular expressions: $$\eqaligneno{ R^{**} &\cong R^{*}\cr (R + S)^{*} &\cong (R^{*} + S^{*})^{*}\cr (R + S)^{*} &\cong (R^{*}S^{*})^{*}\cr (R + S)^{*} &\cong (R^{*}S)^{*}R^{*}\cr }$$ \vspace {0.25cm}\noindent {\bf Problem A2.} Recall that a homomorphism $\mapdef{h}{\Sigma^*}{\Delta^*}$ is a function such that $h(uv) = h(u)h(v)$ for all $u, v\in\Sigma^*$. Given any language $L\subseteq \Sigma^*$, we define $h(L)$ as $$h(L) = \{h(w)\ |\ w\in L\}.$$ Given any language $L'\subseteq \Delta^*$, we define $h^{-1}(L')$ as $$h^{-1}(L') = \{w\in \Sigma^*\ | \ h(w) \in L'\}.$$ \medskip Prove that if $L\subseteq \Sigma^*$ and $L'\subseteq \Delta^*$ are regular languages, then so are $h(L)$ and $h^{-1}(L')$. \medskip\noindent {\bf Problem A3.} Construct an NFA accepting the language $L = \{aa, aaa\}^*$. Apply the subset construction to get a DFA accepting $L$. \vspace {0.25cm} ``B problems'' must be turned in. \vspace{0.25cm}\noindent {\bf Problem B1 (25 pts).} Let $\Sigma = \{a_1,\ldots, a_n\}$ be an alphabet of $n$ symbols. \medskip (a) Construct an NFA with $2n+1$ (or $2n$) states accepting the set $L_n$ of strings over $\Sigma$ such that, every string in $L_n$ has an odd number of $a_i$, for some $a_i\in\Sigma$. Equivalently, if $L_{n}^{i}$ is the set of all strings over $\Sigma$ with an odd number of $a_i$, then $L_n = L_{n}^{1}\cup \cdots \cup L_{n}^{n}$. \medskip (b) Prove that there is a DFA with $2^n$ states accepting the language $L_n$. \medskip (c) Prove that every DFA accepting $L_n$ has at least $2^n$ states. \medskip\noindent {\it Hint\/}: If a DFA $D$ with $k < 2^n$ states accepts $L_n$, show that there are two strings $u, v$ with the property that, for some $a_i\in\Sigma$, $u$ contains an odd number of $a_i$'s, $v$ contains an even number of $a_i$'s, and $D$ ends in the same state after processing $u$ and $v$. From this, conclude that $D$ accepts incorrect strings. \vspace{0.25cm}\noindent {\bf Problem B2 (25 pts).} (a) Let $T = \{0, 1, 2\}$, let $C$ be the set of $20$ strings of length three over the alphabet $T$, \[ C = \{u\in T^3 \mid u \notin \{110, 111, 112, 101, 121, 011, 211\}\}, \] let $\Sigma = \{0, 1, 2, c\}$ and consider the language \[ L_M = \{w \in \Sigma^* \mid w = u_1cu_2c \cdots cu_n,\, n \geq 1, u_i \in C\}. \] Prove that $L$ is regular. \medskip (b) The language $L_M$ has a geometric interpretation as a certain subset of $\reals^3$ (actually, $\rats^3$), as follows: Given any string, $w = u_1cu_2c \cdots cu_n \in L_M$, denoting the $j$th character in $u_i$ by $u_i^j$, where $j\in \{1, 2, 3\}$, we obtain three strings \begin{eqnarray*} w^1 & = & u_1^1u_2^1 \cdots u_n^1 \\ w^2 & = & u_1^2u_2^2 \cdots u_n^2 \\ w^3 & = & u_1^3u_2^3 \cdots u_n^3. \end{eqnarray*} For example, if $w = 012c001c222c122$ we have $w^1 = 0021$, $w^2 = 1022$, and $w^3 = 2122$. Now, a string $v\in T^+$ can be interpreted as a decimal real number written in base three! Indeed, if \[ v = b_1b_2\cdots b_k, \quad\hbox{where}\quad b_i\in \{0, 1, 2\} = T\>\> (1\leq i \leq k), \] we interpret $v$ as $n(v) = 0.b_1b_2\cdots b_k$, i.e., \[ n(v) = b_1 3^{-1} + b_2 3^{-2} + \cdots + b_k 3^{-k}. \] Finally, a string, $w = u_1cu_2c \cdots cu_n \in L_M$, is interpreted as the point, $(x_w, y_w, z_w)\in \reals^3$, where \[ x_w = n(w^1),\> y_w = n(w^2),\> z_w = n(w^3). \] Therefore, the language, $L_M$, is the encoding of a set of rational points in $\reals^3$, call it $M$. This turns out to be the rational part of a fractal known as the {\it Menger sponge\/}. \medskip Explain the best you can what are the recursive rules to create the Menger sponge, starting from a unit cube in $\reals^3$. Draw some pictures illustrating this process and showing approximations of the Menger sponge. \medskip\noindent {\bf Extra Credit (20 points).} Write a computer program to draw the Menger sponge (based on the ideas above). \vspace {0.25cm}\noindent {\bf Problem B3 (50 pts).} Recall that for two regular expressions $R$ and $S$, $R\cong S$ means that $\s{L}[R] = \s{L}[S]$, i.e. $R$ and $S$ denote the same language. \medskip (i) Show that if $R \cong S^{*}T$, then $R \cong SR + T$. \medskip (ii) Assume that $\epsilon$ (the empty string) is not in the language $\s{L}[S]$ denoted by the regular expression $S$. \medskip Show that if $R \cong SR + T$, then $R \cong S^{*}T$. \medskip\noindent {\it Hint\/}: Prove that $x \in \s{L}[R]$ if and only if $x \in \s{L}[S^{*}T]$, by observing that $R \cong SR + T$ implies that for every $k\geq 0$, $$R \cong S^{k+1}R + (S^{k} + S^{k-1} + \ldots + S^{2} + S + \epsilon)T,$$ and that since $\epsilon \notin \s{L}[S]$, every string in $\s{L}[S^{k+1}R]$ has length at least $k+1$. \medskip (iii) Consider the following system of equations where $X_1,\ldots,X_n$ are variables standing for regular expressions, and the $S_{i, j}$ and the $T_i$ are regular expressions: $$\eqaligneno{ X_1 &\cong S_{1, 1}X_1 + \cdots + S_{1, n}X_n + T_1,\cr \cdots &\cong \cdots \cr X_n &\cong S_{n, 1}X_1 + \cdots + S_{n, n}X_n + T_n.\cr }$$ If $\epsilon\notin\s{L}[S_{i, j}]$ for all $i, j$, $1\leq i, j \leq n$, prove that this system has a unique solution. Do you see any connection between this problem and the node elimination algorithm? \medskip\noindent {\it Hint\/}: Eliminate the $X_i$ one by one. \vspace {0.5cm}\noindent {\bf Problem B4 (20 pts).} Let $R$ be any regular language over some alphabet $\Sigma$. Prove that the language $$L = \{u\ \mid \exists v\in\Sigma^*,\, uv\in R,\, |u| = |v|\}$$ is regular \vspace{0.25cm}\noindent {\bf Problem B5 (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 (e) If $M$ is an $a$-transducer from $\Sigma^*$ to $\Delta^*$ prove that for any regular language, $L'\subseteq \Delta^*$, the language $M^{-1}(L')$ is also regular (see the definition of $M^{-1}(L')$ in the class notes). \vspace {0.25cm}\noindent {\bf Problem B6 (60 pts).} ({\it Free generation of regular expressions\/}) The definition of the set $\s{R}(\Sigma)$ of regular expressions over an alphabet $\Sigma$ can be formalized in the following way: First, define the new alphabet \[\Delta = \Sigma \cup\{(, ), +, \cdot, *, \epsilon, \emptyset\}.\] Let $\mapdef{C_{+}}{\Delta^*\times \Delta^*}{\Delta^*}$, $\mapdef{C_{\cdot}}{\Delta^*\times \Delta^*}{\Delta^*}$, and $\mapdef{C_{*}}{\Delta^*}{\Delta^*}$ be the functions defined so that \begin{eqnarray*} C_{+}(u, v) & = & (u + v )\\ C_{\cdot}(u, v) & = & (u \cdot v )\\ C_{*}(u) & = & u*, \end{eqnarray*} for all $u, v\in \Delta^*$. Let \begin{eqnarray*} \s{R}(\Sigma)_0 & = & \Sigma \cup \{\epsilon, \emptyset\}\\ \s{R}(\Sigma)_{n+1} & = & \s{R}(\Sigma)_{n} \cup \{C_{+}(u, v),\> C_{\cdot}(u, v),\> C_{*}(u) \mid u, v \in \s{R}(\Sigma)_{n}\}, \end{eqnarray*} and finally, let \[\s{R}(\Sigma) = \bigcup_{n \geq 0} \s{R}(\Sigma)_{n}.\] We wish to prove that the functions $C_{+}$, $C_{\cdot}$, $C_{*}$ are injective when restricted to $\s{R}(\Sigma)$, which means that if \[C_{+}(u, v) = C_{+}(u', v')\] for any $u, v, u', v' \in \s{R}(\Sigma)$, then $u = u'$ and $v = v'$, similarly for $C_{\cdot}$, and if \[C_{*}(u) = C_{*}(u')\] for any $u, u'\in \s{R}(\Sigma)$, then $u = u'$. We also wish to prove that the sets $C_{+}(\s{R}(\Sigma), \s{R}(\Sigma))$, $C_{\cdot}(\s{R}(\Sigma), \s{R}(\Sigma))$, and $C_{*}(\s{R}(\Sigma))$, are pairwise disjoint. \medskip For this, we introduce the ``head deficiency function'', $K$, defined as follows: \begin{eqnarray*} K(+) & = & -1\\ K(\cdot) & = & -1\\ K(*) & = & 0\\ K(a) & = & 1 \quad(a\in \Sigma)\\ K(\emptyset) & = & 1\\ K(\epsilon) & = & 1\\ K(``(\hbox{''}) & = & 1\\ K(``)\hbox{''}) & = & -1. \end{eqnarray*} This function is extended to $\Delta^+$ in the obvious way, i.e., \[K(w_1\cdots w_k) = K(w_1) + \cdots + K(w_k),\] for all $w_i\in \Delta$ and all $k\geq 1$. \medskip (i) Prove the following properties: \begin{enumerate} \item[(a)] For any regular expression $R\in \s{R}(\Sigma)$, we have $K(R) = 1$. \item[(b)] For any proper suffix $S$ of a regular expression, we have $K(S) \leq 0$. \item[(c)] No proper suffix $S$ of a regular expression is a regular expression. \end{enumerate} \medskip (ii) Using the above, prove that the restrictions of the functions $C_{+}$, $C_{\cdot}$, $C_{*}$ to $\s{R}(\Sigma)$ are injective and that the sets $C_{+}(\s{R}(\Sigma), \s{R}(\Sigma))$, $C_{\cdot}(\s{R}(\Sigma), \s{R}(\Sigma))$, and $C_{*}(\s{R}(\Sigma))$, are pairwise disjoint. \medskip (iii) Prove that $\s{R}(\Sigma)_{n+1} \not= \s{R}(\Sigma)_{n}$ for all $n \geq 0$, and that $C_{+}(u, v)\notin \s{R}(\Sigma)_n$, $C_{\cdot}(u, v)\notin \s{R}(\Sigma)_n$, and $C_{*}(u)\notin \s{R}(\Sigma)_n$, for all $u, v\in \s{R}(\Sigma)_{n} - \s{R}(\Sigma)_{n-1}$ and for all $n\geq 0$ (setting $\s{R}(\Sigma)_{-1} = \emptyset$). \medskip (iv) Recall that the set $R(\Sigma)$ of regular languages over $\Sigma$ is defined inductively as follows: \[R(\Sigma)_0 = \{\{a_1\}, \ldots, \{a_m\}, \{\epsilon\}, \emptyset\},\] where $\Sigma = \{a_1, \ldots, a_m\}$, \[R(\Sigma)_{n+1} = R(\Sigma)_{n} \cup \{L_1\cup L_2,\> L_1\cdot L_2,\> L^* \mid L_1, L_2, L \in R(\Sigma)_{n}\},\] and \[R(\Sigma) = \bigcup_{n \geq 0} R(\Sigma)_n.\] \medskip The interpretation of regular expressions as regular languages is given by the function, $\mapdef{\s{L}}{\s{R}(\Sigma)}{R(\Sigma)}$, defined recursively as follows: \begin{eqnarray*} \s{L}[a_i] & = & \{a_i\}\\ \s{L}[\epsilon] & = & \{\epsilon\}\\ \s{L}[\emptyset] & = & \emptyset\\ \s{L}[(R_1 + R_2)] & = & \s{L}[R_1] \cup \s{L}[R_2] \\ \s{L}[(R_1 \cdot R_2)] & = & \s{L}[R_1] \cdot \s{L}[R_2] \\ \s{L}[R^*] & = & (\s{L}[R])^*. \end{eqnarray*} Prove that the function $\s{L}$ is indeed well-defined. \medskip\noindent {\it Hint\/}. Define a sequence of functions, $\mapdef{\s{L}_n}{\s{R}(\Sigma)_n}{R(\Sigma)}$, by induction using (ii) and (iii), and let $\s{L} = \bigcup_{n \geq 0} \s{L}_n$. You will have to make sense of all of this. \medskip (v) (Regular expressions in prefix notation) Define the new alphabet \[\Delta = \Sigma \cup\{+, \cdot, *, \epsilon, \emptyset\}.\] Let $\mapdef{C_{+}}{\Delta^*\times \Delta^*}{\Delta^*}$, $\mapdef{C_{\cdot}}{\Delta^*\times \Delta^*}{\Delta^*}$, and $\mapdef{C_{*}}{\Delta^*}{\Delta^*}$ be the functions defined so that \begin{eqnarray*} C_{+}(u, v) & = & +\, u v \\ C_{\cdot}(u, v) & = & \cdot\, u v \\ C_{*}(u) & = & *u, \end{eqnarray*} for all $u, v\in \Delta^*$. Let \begin{eqnarray*} \s{R}(\Sigma)_0 & = & \Sigma \cup \{\epsilon, \emptyset\} \\ \s{R}(\Sigma)_{n+1} & = & \s{R}(\Sigma)_{n} \cup \{C_{+}(u, v),\> C_{\cdot}(u, v),\> C_{*}(u) \mid u, v \in \s{R}(\Sigma)_{n}\}, \end{eqnarray*} and finally, let \[\s{R}(\Sigma) = \bigcup_{n \geq 0} \s{R}(\Sigma)_{n}.\] Define the ``tail deficiency function'', $K$, as before: \begin{eqnarray*} K(+) & = & -1\\ K(\cdot) & = & -1\\ K(*) & = & 0\\ K(a) & = & 1 \quad(a\in \Sigma)\\ K(\emptyset) & = & 1\\ K(\epsilon) & = & 1, \end{eqnarray*} and extend it to $\Delta^+$ in the obvious way. Redo questions (i)--(iv) for regular expressions in prefix notation. \medskip (vi) This time, consider the alphabet \[\Delta = \Sigma \cup\{+, \cdot, *, \epsilon, \emptyset\}\] and the functions $\mapdef{C_{+}}{\Delta^*\times \Delta^*}{\Delta^*}$, $\mapdef{C_{\cdot}}{\Delta^*\times \Delta^*}{\Delta^*}$, and $\mapdef{C_{*}}{\Delta^*}{\Delta^*}$ defined so that \begin{eqnarray*} C_{+}(u, v) & = & u + v \\ C_{\cdot}(u, v) & = & u\cdot v \\ C_{*}(u) & = & u*, \end{eqnarray*} for all $u, v\in \Delta^*$. \medskip Show that properties (b) and (c) of (i) fail, that (ii) also fails, and that $\s{L}$ cannot be defined properly. \medskip (vii) {\bf Extra credit (20 pts).} Consider the alphabet \[\Delta = \Sigma \cup\{), +, \cdot, *, \epsilon, \emptyset\}\] and the functions $\mapdef{C_{+}}{\Delta^*\times \Delta^*}{\Delta^*}$, $\mapdef{C_{\cdot}}{\Delta^*\times \Delta^*}{\Delta^*}$, and $\mapdef{C_{*}}{\Delta^*}{\Delta^*}$ defined so that \begin{eqnarray*} C_{+}(u, v) & = & u + v) \\ C_{\cdot}(u, v) & = & u\cdot v) \\ C_{*}(u) & = & u*, \end{eqnarray*} for all $u, v\in \Delta^*$. \medskip Redo questions (i)--(iv) for these strange regular expressions! \vspace {0.25cm}\noindent {\bf Problem B7 (40 pts).} Let $D=(Q,\Sigma,\delta,q_{0},F)$ be a deterministic finite automaton. Define the relations $\approx$ and $\sim$ on $\Sigma^{*}$ as follows: $$\displaylines{ x \approx y\quad\hbox{if and only if},\quad\hbox{for all}\quad p\in Q,\cr \delta^{*}(p,x) \in F\quad\hbox{iff}\quad \delta^{*}(p,y) \in F,\cr}$$ and $$x \sim y\quad\hbox{if and only if},\quad\hbox{for all}\quad p\in Q,\quad \delta^{*}(p,x) = \delta^{*}(p,y).$$ \medskip (a) Show that $\approx$ is a left-invariant equivalence relation and that $\sim$ is an equivalence relation that is both left and right invariant. (A relation $R$ on $\Sigma^{*}$ is {\it left invariant\/} iff $uRv$ implies that $wuRwv$ for all $w \in \Sigma^{*}$, and $R$ is {\it right invariant\/} iff $uRv$ implies that $uwRvw$ for all $w \in \Sigma^{*}$.) \medskip (b) Let $n$ be the number of states in $Q$ (the set of states of $D$). Show that $\approx$ has at most $2^{n}$ equivalence classes and that $\sim$ has at most $n^{n}$ equivalence classes. \medskip (c) Given any language $L\subseteq \Sigma^*$, define the relations $\lambda_L$ and $\mu_L$ on $\Sigma^{*}$ as follows: $$u\, \lambda_L\, v\quad\hbox{iff},\quad\hbox{for all}\quad z\in \Sigma^* ,\quad zu \in L\quad\hbox{iff}\quad zv \in L,$$ and $$u\, \mu_L\, v\quad\hbox{iff},\quad\hbox{for all}\quad x, y\in\Sigma^*,\quad xuy \in L\quad\hbox{iff}\quad xvy \in L.$$ \medskip Prove that $\lambda_L$ is left-invariant, and that $\mu_L$ is left and right-invariant. Prove that if $L$ is regular, then both $\lambda_L$ and $\mu_L$ have a finite number of equivalence classes. \medskip {\it Hint\/}: Show that the number of classes of $\lambda_L$ is at most the number of classes of $\approx$, and that the number of classes of $\mu_L$ is at most the number of classes of $\sim$. \vspace{0.5cm}\noindent {\bf TOTAL: 270 + 40 points.} \end{document}