\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} \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 Summer 1, 2006 \hspace*{0.4cm} CIS 511}}\\ \vspace{1cm} {\Large\bf Introduction to the Theory of Computation\\ Jean Gallier \\ \vspace{0.5cm} Homework 4}\\[10pt] June 13, 2006; Due June 22, 2006\\ \end{center} ``A problems'' are for practice only, and should not be turned in. \vspace {0.25cm} \noindent {\bf Problem A1.} Give constructions proving that for any PDA $M$, the acceptance modes $T(M)$, $N(M)$, and $L(M)$, are equivalent. \vspace {0.25cm} \noindent {\bf Problem A2.} (i) Given any set $X$, for any two subsets $A, B\subseteq X$, prove that $A \subseteq B$ iff $A\cap \ptb{B} = \emptyset$, where $\ptb{B}$ denotes the complement of $B$ in $X$. \medskip (ii) Sketch an algorithm to test whether $L(G) \subseteq L(D)$, where $G$ is a context-free grammar and $D$ is a DFA. \vspace {1cm} ``B problems'' must be turned in. \vspace {0.25cm}\noindent {\bf Problem B1 (60 pts).} A context-free grammar, $G=(V,\Sigma,P,S)$, is {\it linear\/} iff for every production $(A \rightarrow \alpha)\in P$, $$\alpha \in \Sigma^{*}N\Sigma^{*}\cup\Sigma^{*},$$ where $N = V-\Sigma$. A language, $L$, is a {\it linear context-free language\/} iff there is some linear context-free grammar, $G$, such that $L=L(G)$. \medskip (a) Recall that for any string, $w\in \Sigma^*$, the string $w^R$ denotes the reversal of the string $w$, i.e., the string $w$ written in reverse order ($\epsilon^R = \epsilon$). Prove that the language \\ $L_{0} = \{ww^{R}\mid w \in \{a,b\}^{*}\}$ is linear context-free. \medskip (b) Given any regular language, $L \subseteq \Sigma^*$, prove that $L^R = \{w^R \mid w\in L\}$ is also regular. \medskip (c) Let $G=(V,\Sigma,P,S)$ be a {\it linear context-free\/} grammar. Assume that the set of productions $P$ contains $p$ productions and that it is ordered in some fashion. Each production is named $p_{i}$, with $1 \leq i \leq p$. Let $\Delta= \{\delta_{1},\ldots,\delta_{p}\}$ be a set in one-to-one correspondence with the set of productions $P$ and assume that $\Delta$ is disjoint from $V$. The language $R \subseteq \Delta^{*}$ is defined as follows: $$\displaylignes{ R=\{\delta_{i_{1}}\cdots\delta_{i_{n}}\mid n \geq 1,\quad \hbox{there is a derivation}\ S \Longrightarrow \alpha_{1} \Longrightarrow\ \cdots\ \Longrightarrow \alpha_{n}, \hfill\cr \hfill \hbox{such that}\quad \alpha_{n} \in \Sigma^{*} \quad\hbox{and the production applied at the $k$-th step is}\ p_{i_{k}}\}. \cr }$$ Let $h_{1}, h_{2} \co \Delta^{*} \rightarrow \Sigma^{*}$ be the homomorphisms defined as follows: For any $p_{i} \in P$, \begin{enumerate} \item[(1)] If $p_{i}$ is of the form $A \rightarrow uBv$, where $A, B \in N$, and $u, v \in \Sigma^{*}$, then $h_{1}(\delta_{i})=u$ and $h_{2}(\delta_{i})=v$; \item[(2)] If $p_{i}$ is of the form $A \rightarrow w$, where $A\in N$ and $w \in \Sigma^{*}$, then choose any $u, v \in \Sigma^{*}$ such that $w=uv$, and let $h_{1}(\delta_{i})=u$ and $h_{2}(\delta_{i})=v$. \end{enumerate} Prove that for any $k$, with $1 \leq k \leq n-1$, $$\alpha_{k} = h_{1}(\delta_{i_{1}}\cdots\delta_{i_{k}})Bh_{2} (\delta_{i_{k}}\cdots\delta_{i_{1}}),$$ for some $B \in N$, and that $$\alpha_{n} = h_{1}(\delta_{i_{1}}\cdots\delta_{i_{n}})h_{2} (\delta_{i_{n}}\cdots\delta_{i_{1}}).$$ \medskip Conclude that $L(G)=\{h_{1}(w)h_{2}(w^{R})\mid w \in R\}$, for some language $R$ over $\Delta$. \medskip (d) Prove that the language $R$ defined in (c) is regular. %\medskip\noindent %{\it Hint\/}: Construct a right-linear grammar. \medskip (e) Given a linear context-free language, $L=L(G)$, from questions (c) and (d), we know that there is a regular language $R$ and two homomorphisms $h_{1}, h_{2}$, such that $$L=\{h_{1}(w)h_{2}(w^{R})\mid w \in R\}.$$ \medskip Let $\Omega=\{\omega_{1},\ldots,\omega_{p}\}$ be a set in one-to-one correspondence with $\Delta$ and such that $\Omega$ is disjoint from $V$ and $\Delta$. Let $f \co \Delta^{*} \rightarrow \Omega^{*}$ be the homomorphism determined by defining $f(\delta_{i})=\omega_{i}$, for all $i$, with $1 \leq i \leq p$. Let $S$ be the regular language \[ S = \{f(w)^{R}\mid w \in R\} = f(R)^R, \] where $R$ is the regular set of question (c). Also, let $g_{1} \co (\Delta \cup \Omega)^{*} \rightarrow \Sigma^{*}$ be the homomorphism determined by defining \[ g_{1}(\delta_{i})=h_{1}(\delta_{i}) \quad\hbox{and}\quad g_{1}(\omega_{i})=h_{2}(\delta_{i}). \] Finally, let $g_{2} \co (\Delta \cup \Omega)^{*} \rightarrow \{a,b\}^{*}$ be the homomorphism determined by defining \[ g_{2}(\delta_{i})=a^{i}b \quad\hbox{and}\quad g_{2}(\omega_{i})=ba^{i}, \] for all $i$, with $1 \leq i \leq p$. \medskip Prove that $$g_{2}^{-1}(L_{0})\cap RS = \{w_{1}w_{2}\mid w_{1} \in R,\quad w_{2} \in S,\quad\hbox{and}\quad f(w_{1})=w_{2}^{R}\},$$ where $L_{0}$ is the language of question (a), $R$ is defined in question (c), and $S$ is defined above in (e). From this, prove that $$L = g_{1}(g_{2}^{-1}(L_{0})\cap RS).$$ \medskip Hence, prove that every linear context-free language can be obtained from the language $L_{0} = \{ww^{R}\mid w \in \{a,b\}^{*}\}$ by homomorphism, inverse homomorphism, and intersection with regular languages. \medskip\noindent {\it Remark\/}: In fact, it can be shown that the family of linear context-free languages is the least class of languages with these properties. %\medskip\noindent %{\bf Extra Credit (50 pts).} %Using (e), prove that the language $\{a^mb^ma^nb^n \mid m, n\geq 1\}$ %is not linear-context-free. %\medskip\noindent %{\it Hint\/}. First, prove that if %$\mapdef{h_i}{\Sigma}{\Delta_i}$ are homomorphisms ($i = 1, 2$), %$c$ is a new symbol not in $\Sigma\cup \Delta_1\cup \Delta_2$, %and $R\subseteq \Sigma^*$ is a regular language, then %$\{h_1(w)ch_2(w) \mid w\in R\}$ is a linear context-free language. %Then, use some suitable $a$-transductions. This is hard! \vspace {0.25cm} \noindent {\bf Problem B2 (50 pts).} Let $L\subseteq \{a\}^*$ be a context-free language. Prove that $L$ is actually a regular language. Proceed as follows: If $L$ is finite, this is obvious, thus, assume that $L$ is infinite. Let $L = L(G)$, for some CFG $G$. \medskip (i) Let $K > 1$ be the constant of the pumping lemma for $G$, and let $r = K!$. Prove the following fact: for every $w\in L$, if $|w| \geq K$, then $$\{w a^{rn} \ \mid\ n \geq 0\} \subseteq L.$$ \medskip (ii) For every $i$ such that $0 \leq i < r$, let $$L_i = \{a^n \ \mid\ a^n\in L,\, n \geq K,\, n \equiv i \bmod r\}.$$ Clearly, $$L = \{a^n \ \mid\ a^n \in L,\, n < K\} \cup \bigcup_{i = 0}^{r-1} L_i.$$ If $L_i\not=\emptyset$, let $z_i$ be the shortest string in $L_i$. Prove that $$L_i = \{z_i a^{rm}\ \mid \ m \geq 0\}.$$ Conclude that $L$ is regular. \medskip (iii) Prove that it is decidable whether $L_i = \emptyset$ (i.e., describe (concisely) an algorithm). \medskip (iv) Given a context-free language $L$ over $\{a, b\}$, prove that it is decidable whether \\ $\{a\}^* \subseteq L$ (i.e., describe (concisely) an algorithm). \vspace {0.25cm} \noindent {\bf Problem B3 (60 pts).} Give pushdown automata for the following languages: \medskip (a) $L_{4} = \{wcw^{R}\ |\ w \in \{a,b\}^{*}\}$\ ($w^{R}$ denotes the reversal of $w$) \medskip (b) $L_{5} = \{ww^{R}\ |\ w \in \{a,b\}^{*}\}$ \medskip (c) $L_{6} = \{a^{m}b^{n}\ |\ 1 \leq m \leq n \leq 3m\}$ \medskip (d) $L_{7} = \{a^{n}cb^{n}\ |\ n \geq 1\}\cup \{a^{n}db^{2n}\ |\ n \geq 1\}$ \medskip (e) $L_{8} = \{a^{2m}b^{n}a^{2m}b^{p}\ |\ m, n, p \geq 1\} \cup \{a^{m}b^{3n}a^{p}b^{3n}\ |\ m, n, p \geq 1\}$ \medskip (f) $L_9 = \{xcy \ |\ |x| = |y|,\, x, y\in \{a, b\}^*\}$ \medskip Whenever possible, give a DPDA. In each case, give a brief justification of the fact that your PDA generates the desired language. \vspace{0.25cm} \noindent {\bf Problem B4 (40 pts).} Use the pumping lemma (or Ogden's lemma) to show that the following languages are not context-free: \medskip $L_{1} = \{a^mb^nc^p\ | \ 1 \leq m < n < p\}$ \medskip $L_{2} = \{a^nb^nc^p\ | \ n,p \geq 1, p \not= n\}$ \vspace{0.25cm}\noindent {\bf Problem B5 (30 pts).} Given $\Sigma = \{a\}$, give a Turing machine accepting $$L = \{a^{2^{n}} \mid n\geq 1\}.$$ \vspace{0.25cm} \noindent {\bf Problem B6 (30 pts).} {\it Ackermann's function\/} $A$ is defined recursively as follows: \[\eqaligneno{ A(0,\, y) &= y + 1,\cr A(x + 1,\, 0) &= A(x,\, 1),\cr A(x + 1,\, y + 1) &= A(x,\, A(x + 1, y)).\cr }\] Prove that \[\eqaligneno{ A(0,\, x) &= x + 1,\cr A(1,\, x) &= x + 2,\cr A(2,\, x) &= 2x + 3,\cr A(3,\, x) &= 2^{x + 3} - 3,\cr }\] and \[A(4, x) = \supexpo{2}{16}{x}\> - 3,\] with $A(4, 0) = 16 - 3 = 13$. Equivalently (and perhaps less confusing) \[A(4, x) = \supexpo{2}{2}{x+3}\> - 3.\] \vspace{0.5cm}\noindent {\bf TOTAL: 270 points.} \end{document}