\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 2}\\[10pt] February 4, 2003; Due Febuary 20, beginning of class\\ \end{center} ``A problems'' are for practice only, and should not be turned in. \vspace {0.25cm} \noindent {\bf Problem A1.} Recall that two regular expressions $R$ and $S$ are equivalent, denoted by $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 }$$ \medskip\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^*$ is regular, then so is $h(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.5cm} ``B problems'' must be turned in. \vspace {0.25cm}\noindent {\bf Problem B1 (40 pts).} (a) Prove again that the intersection, $L_1\cap L_2$, of two regular languages, $L_1$ and $L_2$, is regular, {\bf using the Myhill-Nerode characterization\/} of regular languages. \medskip (b) Let $\mapdef{h}{\Sigma^*}{\Delta^*}$ be a homomorhism, as in A2. For any regular language, $L' \subseteq \Delta^*$, prove that $h^{-1}(L')$ is regular, {\bf using the Myhill-Nerode characterization\/} of regular languages. Prove that the number of states of any minimal DFA for $h^{-1}(L')$ is at most the number of states of any minimal DFA for $L'$. Can it be strictly smaller? \vspace {0.25cm}\noindent {\bf Problem B2 (120 pts).} The purpose of this problem is to investigate the notion of mapping between NFA's. It is assumed that all DFA's and NFA's considered in this problem are defined over some fixed alphabet $\Sigma$. For simplicity, we also assume that we are considering NFA's {\it without\/} $\epsilon$-transitions. \medskip Given two NFA's $N_1 = (Q_1, \Sigma, \delta_1, q_{0 1}, F_1)$ and $N_2 = (Q_2, \Sigma, \delta_2, q_{0 2}, F_2)$, we say that a relation $\varphi\subseteq Q_1\times Q_2$ is a {\it simulation of $N_1$ by $N_2$\/}, denoted by $\mapdef{\varphi}{N_1}{N_2}$, if the following properties hold: \begin{enumerate} \item[(1)] $(q_{0 1}, q_{0 2}) \in \varphi$. \item[(2)] Whenever $(p, q)\in \varphi$, for every $r\in \delta_1(p, a)$, there is some $s\in \delta_2(q, a)$ so that $(r, s)\in \varphi$, for all $a\in\Sigma$. \item[(3)] Whenever $(p, q)\in \varphi$, if $p\in F_1$ then $q\in F_2$. \end{enumerate} \medskip (i) If $N_1$ and $N_2$ are actually DFA's, show that a map $\mapdef{\varphi}{N_1}{N_2}$ of DFA's is a simulation of $N_1$ by $N_2$ (viewing the function $\varphi$ as a relation, in the obvious way). \medskip (ii) Let $\mapdef{\varphi}{N_1}{N_2}$ be a simulation of $N_1$ by $N_2$. Prove that for every $w\in \Sigma^*$, for every $q_1\in \delta_1^*(q_{0 1}, w)$, there is some $q_2\in \delta_2^*(q_{0 2}, w)$, so that \[(q_1, q_2)\in \varphi.\] Conclude that $L(N_1) \subseteq L(N_2)$. \medskip (iii) %(Alin Deutsch, Val Tannen) If $N_1$ is an NFA and $D_2$ is a DFA, prove that if $L(N_1) \subseteq L(D_2)$, then there is some simulation $\mapdef{\varphi}{N_1}{D_2}$ of $N_1$ by $D_2$. \medskip\noindent {\it Hint\/}. Consider the relation $\varphi = \{(q_1, q_2)\ \mid \ q_1\in \delta_1^*(q_{0 1}, w),\, q_2 = \delta_2^*(q_{0 2}, w),\, w\in \Sigma^*\}$. \remark If $D_1$ and $D_2$ are DFA's and $L(D_1) \subseteq L(D_2)$, then there may not exist any DFA map from $D_1$ to $D_2$, but the above shows that there is always a simulation of $D_1$ by $D_2$. \medskip (iv) Give a counter-example showing that (iii) is generally {\it false\/} for NFA's, i.e., if $N_1$ and $N_2$ are both NFA's and $L(N_1) \subseteq L(N_2)$, there may not be any simulation $\mapdef{\varphi}{N_1}{N_2}$. \medskip In order to salvage (iii), we modify conditions (2) and (3) of the definition of a simulation $\mapdef{\varphi}{N_1}{N_2}$. Let $N_1$, $N_2$ be NFA's, and let $n_1$ be the number of states of $N_1$ and $n_2$ the number of states of $N_2$. Then, we say that $\mapdef{\varphi}{N_1}{N_2}$ is a {\it generalized simulation,\/} for short, a {\it $g$-simulation\/}, if \begin{enumerate} \item[(1)] $(q_{0 1}, q_{0 2}) \in \varphi$. \item[(2b)] Whenever $(p, q)\in \varphi$, for every $r\in \delta_1(p, a)$, if $\delta_2(q, a) \not=\emptyset$, then there is some $s\in \delta_2(q, a)$ so that $(r, s)\in \varphi$, for all $a\in\Sigma$. \item[(3b)] For all $w\in \Sigma^*$ with $|w| < n_12^{n_2}$, for every $q_1\in \delta_1^*(q_{0 1}, w)\cap F_1$, there is some $q_2\in \delta_2^*(q_{0 2}, w)\cap F_2$ so that $(q_1, q_2)\in \varphi$. \end{enumerate} \medskip Prove that $L(N_1) \subseteq L(N_2)$ iff there is some $g$-simulation $\mapdef{\varphi}{N_1}{N_2}$. \remark Condition (3b) is very strong, since by itself, it implies that $L(N_1) \subseteq L(N_2)$. Thus, this ``quick fix'' is not very satisfactory. A more natural condition (if any), remains to be found! \medskip (v) We say that $\mapdef{\varphi}{N_1}{N_2}$ is a {\it $g$-bisimulation between $N_1$ and $N_2$\/} if $\varphi$ is a $g$-simulation between $N_1$ and $N_2$ and $\varphi^{-1}$ is a $g$-simulation between $N_2$ and $N_1$ (recall that $\varphi^{-1} = \{(q, p)\in Q_2\times Q_1\ \mid \ (p, q) \in \varphi\}$). \medskip Prove that $L(N_1) = L(N_2)$ iff there is some $g$-bisimulation between $N_1$ and $N_2$. \medskip (vi) We say that an NFA $N$ is {\it trim\/} if for every state $q$, there is some $w\in \Sigma^*$ so that $q\in \delta^*(q_0, w)$. Let $N$ be a trim NFA and $D$ a DFA. Give a counter-example to fact that if a simulation $\mapdef{\varphi}{N}{D}$ exists, then it is unique. \medskip To fix the above problem we define {\it reduced simulations\/}. We say that a simulation $\mapdef{\varphi}{N_1}{N_2}$ is {\it reduced\/}, for short, a {\it $r$-simulation\/}, if for all $(q_1, q_2)\in \varphi$, there is some $w\in \Sigma^*$ with $|w| < n_1n_2$, so that $q_1\in \delta_1^*(q_{0 1}, w)$ and $q_2\in \delta_2^*(q_{0 2}, w)$ ($n_1$ and $n_2$ are the number of states of $N_1$ and $N_2$). \medskip (vii) Let $\mapdef{\varphi}{N_1}{N_2}$ and $\mapdef{\psi}{N_2}{N_3}$ be two simulations. Prove that $\mapdef{\varphi\circ\psi}{N_1}{N_3}$ is also a simulation (where $\varphi\circ \psi$ is the composition of the {\it relations\/} $\varphi$ and $\psi$). Prove that this is {\bf not true} if $\varphi, \psi$ are $r$-simulations. \danger In the rest of this problem, we will be dealing with {\it $r$-simulations\/}. Also, $\circ$ denotes composition of {\it relations\/}. This means that in $\varphi\circ \psi$, the relation $\varphi$ is applied {\it before\/} the relation $\psi$. This is the {\it opposite\/} of the conventional notation for the composition $\psi\circ\varphi$ of {\it functions\/}, where the function $\varphi$ is applied before the function $\psi$. \medskip Say that an $r$-simulation $\mapdef{\varphi}{N_1}{N_2}$ is an {\it isomorphism between $N_1$ and $N_2$\/} if there is a $r$-simulation $\mapdef{\psi}{N_2}{N_1}$ such that $\varphi\circ \psi = \id_{N_1}$ and $\psi\circ \varphi = \id_{N_2}$. What can you conclude if there is an isomorphism $\mapdef{\varphi}{N_1}{N_2}$? Does this imply that $N_1$ and $N_2$ have the same number of states? \medskip (viii) Given an NFA $N$ (without $\epsilon$-transitions), let $\s{D}(N)$ be the trim DFA obtained by applying to $N$ the subset construction given in class (slides, page 45). Observe that the states of $\s{D}(N)$ are the subsets of the form $\delta^*(q_0, w)$, for all $w\in \Sigma^*$. Prove that there is a $r$-simulation $\mapdef{\eta_N}{N}{\s{D}(N)}$. For every DFA $D$, for every $r$-simulation $\mapdef{\varphi}{N}{D}$, prove that there is a unique $r$-simulation $\mapdef{\varphi^{\sharp}}{\s{D}(N)}{D}$ such that $\varphi = \eta_N\circ\varphi^{\sharp}$. \remarks \begin{enumerate} \item Unfortunately, if $\mapdef{\varphi}{N_1}{N_2}$ is an $r$-simulation, \[\varphi\circ \eta_{N_2}\] is {\bf not} necessarily an $r$-simulation! \item Simulations and bisimulations play an important role in models of concurrency and some data base models. \end{enumerate} \medskip\noindent {\bf Open Problem}. Find a reasonable notion of $r$-simulation between NFA's and DFA's, so that the composition of $r$-simulations is an $r$-simulation, and the beginning of (viii) holds. Then, every $r$-simulation $\mapdef{\varphi}{N_1}{N_2}$ yields an $r$-simulation $\mapdef{\s{D}(\varphi)}{\s{D}(N_1)}{\s{D}(N_2)}$ defined by \[\s{D}(\varphi) = (\varphi\circ \eta_{N_2})^{\sharp}.\] \medskip If this can be done, let $\s{DFA}$ be the set of trim DFA's (over $\Sigma$) and let the maps between DFA's be $r$-simulations. Similarly, let $\s{NFA}$ be the set of (trim) NFA's (over $\Sigma$) and let the maps between NFA's be $r$-simulations. Then, there are maps $\mapdef{\s{D}}{\s{NFA}}{\s{DFA}}$ and $\mapdef{\s{N}}{\s{DFA}}{\s{NFA}}$, where $\s{N}(D)$ is the DFA $D$ viewed as an NFA, and $\s{D}(N)$ is the DFA associated with the NFA $N$. A $r$-simulation $\mapdef{\varphi}{D_1}{D_2}$ of DFA's is mapped to the same $r$-simulation $\mapdef{\s{N}(\varphi)}{\s{N}(D_1)}{\s{N}(D_2)}$ viewed as a $r$-simulation of NFA's, and a $r$-simulation $\mapdef{\varphi}{N_1}{N_2}$ of NFA's is mapped to the $r$-simulation $\mapdef{\s{D}(\varphi)}{\s{D}(N_1)}{\s{D}(N_2)}$. Then, $\s{DFA}$ and $\s{NFA}$ would be categories and $\s{D}$ and $\s{N}$ would be adjoint functors. Indeed, there would be natural bijections \[\theta_{N, D}\co \Hom{\s{DFA}}{\s{D}(N)}{D}\rightarrow \Hom{\s{NFA}}{N}{\s{N}(D)},\] for all $D\in \s{DFA}$ and all $N\in \s{NFA}$. \vspace {0.25cm} \noindent {\bf Problem B3 (60 pts).} let $\Sigma$ be an alphabet. For any language $L$ and any string $x\in\Sigma^*$, the {\it left derivative of $L$ w.r.t. $x$\/,} denoted by $x\backslash L$, or $D_x L$, or $\myfrac{dL}{dx}$, is the language \[D_x L = \{y\in \Sigma^*\ |\ xy\in L\}.\] \medskip (1) Prove the following identities for all languages $L$, $A$, $B$ over $\Sigma$: \[ \eqaligneno{ D_{xy} L &= D_y (D_x L),\cr D_{\epsilon} L &= L,\cr D_x(A\cup B) &= D_x A \cup D_x B,\cr } \] and for every symbol $a\in \Sigma$, \[ \eqaligneno{ D_{a} (AB) &= (D_a A) B \cup (A \cap \{\epsilon\}) D_a B,\cr D_a(L^*) &= (D_a L) L^*.\cr } \] Given a regular expression $R$ and a string $x\in\Sigma^*$, we define the (left) derivative $D_x R$ of $R$ w.r.t. $x$ so that \[\s{L}[D_x R] = D_x \s{L}[R].\] We let \[D_{\epsilon} R = R \quad\hbox{and}\quad D_{xa} R = D_a(D_x R)\] where $a\in \Sigma$ and $x\in \Sigma^*$, \[D_a \emptyset = \emptyset, \quad D_a \epsilon = \emptyset, \quad D_a a = \epsilon, \quad D_a b = \emptyset,\] for all $a, b\in \Sigma$, $a\not= b$, \[ \eqaligneno{ D_a((R + S)) &= (D_a R + D_a S),\cr D_a (R^*) &= (D_a R\, R^*),\cr D_a (RS) &= \cases{ (D_a R \> S) & if $\epsilon \notin \s{L}[R]$,\cr ((D_a R \> S) + D_a S)& if $\epsilon \in \s{L}[R]$,\cr } } \] where $R, S$ are any regular expressions. \medskip (2) Give a simple algorithm to decide whether $\epsilon \in \s{L}[R]$, where $R$ is any given regular expression. \medskip Prove that every regular expression has finitely many distinct derivatives (by distinct derivatives, we mean inequivalent derivatives). \medskip\noindent {\it Hint\/}. Use an induction on the number of occurrences of the symbols from $\Sigma \cup \{\epsilon, \emptyset, +, \cdot, *\}$. When $R = (S\cdot T)$, prove that $D_x R$ is equivalent to an expression of the form \[(D_x S\> T + D_{v_1} T + \cdots + D_{v_k} T),\] where for every $i$, $1\leq i \leq k$, there is some $u_i\in \s{L}[S]$ such that $x = u_iv_i$. When $R = S^*$, prove that $D_x R$ is equivalent to an expression of the form \[(D_{v_1} S + \cdots + D_{v_k} S)S^*,\] where for every $i$, $1\leq i\leq k$, there is some $u_i\in \s{L}[S^*]$ such that $x = u_iv_i$. \medskip (3) Assuming that $R$ has $n$ distinct derivatives, prove that every derivative of $R$ belongs to the finite set \[\{D_x R\ |\ x\in \Sigma^*, \ 0\leq |x| < n\}.\] Show that the upper bound on the number of derivatives is a product of towers of exponentials (in terms of the length of $R$). \medskip (4) Prove that if $D$ is a DFA accepting $\s{L}[R]$ and $D$ has $n$ states, then $R$ has at most $n$ distinct derivatives. \medskip If $\nu(R)$ is the number of occurrences in $R$ of the symbols from $\Sigma \cup \{\epsilon, \emptyset, +, \cdot, *\}$, prove that $R$ has at most \[2^{2\nu(R)} \leq 4^{|R|}\] distinct derivatives (where $|R|$ denotes the length of $R$). \medskip (5) If $L$ is any regular language over $\Sigma^*$, prove that the number of states of every minimal DFA for $L$ is equal to the number of distinct derivatives, $D_u(L)$, of $L$. \medskip (6) Prove that the regular expression \[R = (a + b)^* a \underbrace{(a + b) \cdots (a + b)}_{n}\] has $\nu(R) = 3n + 5$ (if we do not count $\cdot$, otherwise, $\nu(R) = 4n + 6$) and that $R$ has $2^{n+1}$ distinct derivatives. \medskip Prove that there is a $2$-state DFA accepting the language denoted by $(a + b)^* a$ and there is an $(n + 2)$-state DFA accepting the language denoted by $\underbrace{(a + b) \cdots (a + b)}_{n}$. \\ Yet, prove that any minimal DFA for the language denoted by $R$ above has $2^{n+1}$ states. \vspace {0.25cm}\noindent {\bf Problem B4 (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.25cm}\noindent {\bf Problem B5 (60 pts).} Let $L$ be any regular language over some alphabet $\Sigma$. Define the languages \begin{eqnarray*} L^{\infty} & = & \bigcup_{k\geq 1} \{w^k \mid w \in L\}, \\ L^{1/\infty} & = & \{w \mid w^k \in L,\quad \hbox{for all $k\geq 1$}\}, \quad\hbox{and} \\ \sqrt{L} & = &\{w \mid w^k \in L,\quad \hbox{for some $k\geq 1$}\}. \end{eqnarray*} Also, for any natural number $k \geq 1$, let \[L^{(k)} = \{w^k \mid w \in L\},\] and \[L^{(1/k)} = \{w \mid w^k \in L\}.\] \medskip (a) Prove that $L^{(1/3)}$ is regular. What about $L^{(3)}$? \medskip (b) Let $k\geq 1$ be any natural number. Prove that there are only finitely many languages of the form $L^{(1/k)} = \{w \mid w^k \in L\}$ and that they are all regular. (In fact, if $L$ is accepted by a DFA with $n$ states, there are at most $2^{n^n}$ languages of the form $L^{(1/k)}$). \medskip (c) Is $L^{1/\infty}$ regular or not? Is $\sqrt{L}$ regular or not? What about $L^{\infty}$? \vspace {0.25cm}\noindent {\bf Problem B6 (40 pts).} Which of the following languages are regular? Justify each answer. \medskip (a) $L_{1}=\{wcw \mid w\in \{a,b\}^{*}\}$ \medskip (b) $L_{2}=\{xy \mid x,y\in \{a,b\}^{*}\ \hbox{and}\ |x| = |y|\}$ \medskip (c) $L_{3}=\{a^{n} \mid n\ \hbox{is a prime number}\}$ \medskip (d) $L_{4} = \{a^mb^n \mid gcd(m, n) = 17\}$. \vspace{0.25cm}\noindent {\bf TOTAL: 360 points.} \end{document}