\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} \def\buildrell#1\over#2{\mathrel{\mathop{\null#1}\limits_{#2}}} \def\rmder#1{{\ \buildrell \Longrightarrow \over{rm}}^{#1}\ } \def\lmder#1{\buildrel #1\over{\buildrell \Longrightarrow \over{lm}}} % \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 4}\\[10pt] March 18, 2003; Due April 1, beginning of class\\ \end{center} ``A problems'' are for practice only, and should not be turned in. \vspace {0.25cm} \noindent {\bf Problem A1.} Given any two context-free languages $L_1$ and $L_2$ over the same alphabet $\Sigma$, prove that $L_1\cup L_2$ and $L_1L_2$ are also context-free. \vspace {0.25cm} \noindent {\bf Problem A2.} 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 (60 pts).} (1) Let $(A, \leq)$ be an $\omega$-complete partial order. Assume we have $m$ functions, $\mapdef{f_i}{A^{m + n}}{A}$, and $n$ functions, $\mapdef{g_j}{A^{n}}{A}$, where $m, n \geq 1$ and where $A^n$ and $A^{m + n}$ are $\omega$-complete partial orders under the componentwise ordering (i.e., $(a_1, \ldots, a_n) \leq (b_1, \ldots, b_n)$ iff $a_i \leq b_i$, for $i = 1, \ldots, n$). Define the functions, $\mapdef{F}{A^{m + n}}{A^{m + n}}$ and $\mapdef{G}{A^{n}}{A^{n}}$, by \[ F_{i}(a_1, \ldots, a_{m + n}) = \cases{ f_i(a_1, \ldots, a_{m + n}) & if $1\leq i \leq m$\cr g_{i - m}(a_{m + 1}, \ldots, a_{m + n}) & if $m + 1\leq i \leq m + n$,\cr } \] and \[ G_j(a_1, \ldots, a_{n}) = g_j(a_1, \ldots, a_{n}),\quad \hbox{for $j = 1, \ldots, n$}. \] If the $f_i$'s and the $g_j$'s are $\omega$-continuous, check that $F$ and $G$ are $\omega$-continuous. Thus, $F$ has a least fixed point, say \[ \gamma = (\alpha', \beta') = (\alpha_1', \ldots, \alpha_m', \beta_1', \ldots, \beta_n') \] and $G$ has a least fixed point, say $\beta = (\beta_1, \ldots, \beta_n)$. We can also consider the function, $\mapdef{F_{\beta}}{A^{m}}{A^{m}}$, given by \[ F_{\beta, i}(a_1, \ldots, a_m) = f_i(a_1, \ldots, a_m, \beta_1, \ldots, \beta_n), \quad\hbox{for $i = 1, \ldots, m$}. \] Check that $F_{\beta}$ is $\omega$-continuous. Thus, $F_{\beta}$ has a least fixed point, say $\alpha = (\alpha_1, \ldots, \alpha_m)$. Prove that $\alpha' = \alpha$ and $\beta' = \beta$. \medskip This shows that the least fixed point of $F$ can be computed in two stages: First, compute the least fixed point of $G$; then, substitute the component of this least fixed point for the last $n$ arguments of $F$ and compute the least fixed point of the resulting function, $F_{\beta}$. \medskip (2) Given any two alphabets $\Sigma, \Delta$, a {\it substitution\/} is a function $\mapdef{\tau}{\Sigma}{2^{\Delta^*}}$ assigning some language $\tau(a) \subseteq \Delta^*$ to every symbol $a\in\Sigma$. A substitution $\mapdef{\tau}{\Sigma}{2^{\Delta^*}}$ is extended to a map $\mapdef{\tau}{2^{\Sigma^*}}{2^{\Delta^*}}$ by first extending $\tau$ to strings using the following definition $$\eqaligneno{ \tau(\epsilon) &= \{\epsilon\},\cr \tau(ua) &= \tau(u)\tau(a),\cr }$$ where $u\in \Sigma^*$ and $a\in\Sigma$, and then to languages by letting $$\tau(L) = \bigcup_{w\in L} \tau(w),$$ for every language $L\subseteq \Sigma^*$. \medskip For example, let $\mapdef{\tau}{\Sigma}{2^{\Sigma^*}}$ be the substitution defined such that $\tau(a) = \{\epsilon, a\}$ for every $a\in \Sigma$. Explain (in words) what $\tau(L)$ is. \medskip In general, prove, {\bf using B1 (1)\/}, that if $L$ is a context-free language and if $\tau(a)$ is a context-free language for every $a\in \Sigma$, then $\tau(L)$ is also a context-free language. Deduce from the above that the context-free languages are closed under homomorphisms. \medskip (3) Are the regular languages closed under substitution by regular languages? \medskip (4) Prove again that if $L$ is a context-free language and if $\tau(a)$ is a context-free language for every $a\in \Sigma$, then $\tau(L)$ is also a context-free language, this time, using CFG's and derivations. \vspace {0.25cm}\noindent {\bf Problem B2 (20 pts).} Given any set $A$, recall that we denote the power set of $A$ by $2^A$. We define the partial order $\leq$ on $2^A\times 2^A$ as follows: For all $A_1, A_2, B_1, B_2 \subseteq A$, \[(A_1, A_2) \leq (B_1, B_2) \quad\hbox{iff}\quad A_1 \subseteq B_1 \quad\hbox{and}\quad A_2 \subseteq B_2. \] (i) Check that the least upper bound of every $\omega$-chain $(X_i, Y_i)_{i \geq 0}$ in $2^A\times 2^A$ is \[\Bigl(\bigcup_{i\geq 0} X_i,\, \bigcup_{i\geq 0} Y_i\Bigr).\] (ii) Now, assume that $A = \Sigma^*$, where $\Sigma$ is some finite alphabet. Prove that union, concatenation and intersection (functions $2^{\Sigma^*} \times 2^{\Sigma^*}\longrightarrow 2^{\Sigma^*}$) are $\omega$-continuous. What about complementation ? (a function $2^{\Sigma^*}\longrightarrow 2^{\Sigma^*}$). \vspace {0.25cm}\noindent {\bf Extra Credit (20 pts).} Prove that the function $\Phi_G$ associated with a context-free grammar $G$ (see the notes, page 41-42) is $\omega$-continuous. \vspace{0.25cm}\noindent {\bf Problem B3 (60 pts).} Let $D = (Q, \Sigma, \delta, q_0, F)$ be a DFA. Consider the following procedure: \begin{enumerate} \item[(1)] Form an NFA, $N$, by reversing all the transitions of $D$, i.e., there is a transition from $p$ to $q$ on input $a\in \Sigma$ in $N$ iff $\delta(q, a) = p$ in $D$. \item[(2)] Apply the subset construction to the NFA, $N$, obtained in (1), taking the start state to be the set $F$ and the only final state of $N$ to be $\{q_0\}$. Then, trim the resulting DFA, obtaining the DFA $D^R$. \end{enumerate} Observe that $L(D^R) = L(D)^R$. \medskip Now, apply the above procedure to $D$, getting $D^R$, and apply this procedure again, to get $D^{RR}$. Prove that $D^{RR}$ is a minimal DFA for $L = L(D)$. \medskip\noindent {\it Hint\/}. First prove that if $\delta_R$ is the transition function of $D^R$, then for every $w\in \Sigma^*$ and for every state, $T$, of $D^R$, \[ \delta_R^*(T, w) = \{q\in Q \mid \delta^*(q, w^R) \in T\}. \] %What can you say about $D^R$ if $D$ is trim? \vspace{0.25cm}\noindent {\bf Problem B4 (60 pts).} Give context-free grammars for the following languages: \medskip (a) $L_{5} = \{ww^{R}\ |\ w \in \{a,b\}^{*}\}$\ ($w^{R}$ denotes the reversal of $w$) \medskip (b) $L_{6} = \{a^{m}b^{n}\ |\ 1 \leq m \leq n \leq 3m\}$ \medskip For any fixed integer $K\geq 2$, \medskip $L_{7} = \{a^{m}b^{n}\ |\ 1 \leq m \leq n \leq Km\}$ \medskip (c) $L_{8} = \{a^{n}b^{n}\ |\ n \geq 1\}\cup \{a^{n}b^{2n}\ |\ n \geq 1\}$ \medskip (d) $L_{9} = \{a^{m}b^{n}a^{m}b^{p}\ |\ m, n, p \geq 1\} \cup \{a^{m}b^{3n}a^{p}b^{3n}\ |\ m, n, p \geq 1\}$ \medskip (e) $L_{10} = \{xcy \ |\ |x| = 3|y|,\, x, y\in \{a, b\}^*\}$ \medskip In each case, give a justification of the fact that your grammar generates the desired language. \vskip 0.25cm \noindent {\bf Problem B5 (40 pts).} Given a context-free language $L$ and a regular language $R$, prove that $L\cap R$ is context-free. \medskip {\bf Do not\/} use PDA's to solve this problem! \medskip\noindent {\it Hint\/}. Without loss of generality, assume that $L = L(G)$, where $G = (V, \Sigma, P, S)$ is in Chomsky normal form, and let $R = L(D)$, for some DFA $D = (Q, \Sigma, \delta, q_0, F)$. Use a kind of cross-product construction as sketched below. Construct a CFG $G_2$ whose set of nonterminals is $Q\times N\times Q\ \cup\{S_0\}$, where $S_0$ is a new nonterminal, and whose productions are of the form: % $$S_0 \rightarrow (q_0, S, f),$$ for every $f\in F$; $$(p, A, \delta(p, a)) \rightarrow a \quad\hbox{iff}\quad (A \rightarrow a) \in P,$$ for all $a\in \Sigma$, all $A\in N$, and all $p\in Q$; $$(p, A, s) \rightarrow (p, B, q)(q, C, s) \quad\hbox{iff}\quad (A \rightarrow BC)\in P,$$ for all $p, q, s\in Q$ and all $A, B, C\in N$; $$S_0 \rightarrow \epsilon \quad\hbox{iff}\quad (S\rightarrow \epsilon) \in P\ \hbox{and}\ q_0\in F.$$ \medskip Prove that for all $p, q\in Q$, all $A\in N$, all $w\in\Sigma^+$, and all $n\geq 1$, $$(p, A, q) \lmder{n}_{G_{2}} w \quad\hbox{iff}\quad A \lmder{n}_{G} w\quad \hbox{and}\quad \delta^*(p, w) = q.$$ Conclude that $L(G_2) = L \cap R$. \vspace {0.25cm}\noindent {\bf Problem B6 (40 pts).} Give context-free grammars for the languages \begin{eqnarray*} L_1 & = & \{xcy\ \mid \ x\not= y,\, x, y\in \{a, b\}^*\}\\ L_2 & = & \{xcy\ \mid\ \ x\not= y^R,\, x, y\in \{a, b\}^*\}. \end{eqnarray*} \vspace{0.25cm}\noindent {\bf TOTAL: 280 points.} \end{document}