\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 Summer 1, 2006 \hspace*{0.4cm} CIS 511}}\\ \vspace{1cm} {\Large\bf Introduction to the Theory of Computation\\ Jean Gallier \\ \vspace{0.5cm} Homework 2}\\[10pt] June 30, 2006; Due June 8, 2006\\ \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 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.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 (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 B3 (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 B4 (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 B5 (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.5cm}\noindent {\bf TOTAL: 240 points.} \end{document}