\documentstyle[11pt]{article}
% frob with the margins
\addtolength{\topmargin}{-1in}
\addtolength{\footskip}{-1in}
\addtolength{\textheight}{2in}
\addtolength{\oddsidemargin}{-.5in}
\addtolength{\evensidemargin}{-.5in}
\addtolength{\textwidth}{1in}
% no page numbers
\pagestyle{empty}
% counter for page numbers
\newcounter{pg}
\setcounter{pg}{2}

% DEFINE THE PROBLEM SET NUMBER
\def\psnum{4}

% DEFINE THE DUE DATE
\def\due{March 8, 1991}

% title command
\newcommand{\mytitle}{{\large\noindent 6.045/18.400 Automata,
Computability, and Complexity \hfill{} Juliet Bourne \\
Problem Set \psnum \hfill{} \due \\}
\vspace{-.6in}
\begin{center} \rule{6in}{.25mm} \end{center}}
% newpage setup command 
\newcommand{\mypage}[1]{\newpage{\large\noindent 6.045/18.400 Automata,
Computability, and Complexity \hfill{} Juliet Bourne \\
Problem Set \psnum \hfill{} \due \\}
\vspace{-.6in}
\begin{center} \rule{6in}{.25mm} \end{center}}
%\newcommand{\mynewpage}{\newpage\noindent
%{\large 6.045/18.400 \hfill{} Juliet Bourne \\
%Problem Set \psnum \hfill{} {\bf Page \thepg} \\}
%\vspace{-.6in}
%\begin{center}
%\rule{6in}{.25mm}
%\end{center}
%\addtocounter{pg}{1}}
% problem command
\newcommand{\prob}[1]{\noindent{\fbox{\large\bf Problem #1}}\vspace{.25in}}
% subproblem command
\newcommand{\subprob}[1]{\vspace{.15in} \noindent{\large\bf #1.}}
% equations commands
\newcommand{\beq}{\vspace*{-.3in}\begin{eqnarray*}}
\newcommand{\eeq}{\end{eqnarray*}}

\newcommand{\mt}{\varepsilon}

\begin{document}

\mytitle

\prob{1: DFA Modeling}

\subprob{a} It can be modelled with a simple two-state finite
automaton. Since the switches change direction with each marble through,
the first marble leaves through C, the second leaves through D, the
third leaves through C, et cetera.

\vspace*{1in}

\subprob{b} This finite automaton accepts the set of all strings with
odd length.

\mypage

\prob{2: Context-Free languages}

\subprob{A} Show that the following languages are context-free by
constructing a context-free grammar for them.

(i) $A = \{ ww^R : w \in \{0,1\}^*\}$

Rules to generate this language: 

\beq
S & \rightarrow & R | T | \mt \\
R & \rightarrow & 0 S 0 \\
T & \rightarrow & 1 S 1 
\eeq

Let $L(G_1) = L(A)$. Therefore, $G_1 = (V, \Sigma , R, S)$ where:

\beq
V & = & \Sigma \cup \{R,T\} \\
\Sigma & = & \{0, 1, \#\} \\
R & = & \{ S \rightarrow R , S \rightarrow T , S \rightarrow \mt
, R \rightarrow 0S0 , T \rightarrow 1S1\}
\eeq

(ii) $C = \{ w : w \in \{0,1\}^*$ such that $w$ does not have an equal
number of 0's and 1's.

Rules to generate this language:

\beq
S & \rightarrow & R | T \\
R & \rightarrow & 0 | 1 R 0 | 0 R 1 | 0 R 0 \\
T & \rightarrow & 1 | 1 T 0 | 0 T 1 | 1 T 1 
\eeq

Let $L(G_2) = L(A)$. Therefore, $G_2 = (V, \Sigma , R, S)$ where:

\beq
V & = & \Sigma \cup \{R,T\} \\
\Sigma & = & \{0, 1, \#\} \\
R & = & \{ S \rightarrow R , S \rightarrow T , R \rightarrow 0 , R
\rightarrow 1R0 , R \rightarrow 0R1 , R \rightarrow 0R0 \\
& & T \rightarrow 1 , T \rightarrow 1T0 , T \rightarrow 0T1 , T
\rightarrow 1T1\}
\eeq

\subprob{B} Let $L = \{ w : w = x\#yx^Rz$, where $x,y,z \in
\{0,1\}^*\}$. Show that $L$ is context-free by constructing a PDA
accepting it.

\noindent Rough algorithm for the PDA:

\begin{enumerate}
\item Read input symbol. If it is \#, go to 2. Otherwise, push it onto
the stack and repeat 1. 
\item Read input until y has been read and then go to 3.
\item Read input. If it matches the top of the stack, then pop the top
of the stack and repeat 3. If the stack is empty, go to 4. 
\item Enter final state. Read the rest of the input, if any.
\end{enumerate}

\mypage

\noindent The PDA $M$ to accept this language would be $M = (K, \Sigma ,
\Gamma , \Delta , s, z_0, F)$ where:

\beq
K & = & \{ s, m, n, f \} \\
\Sigma & = & \{ 0, 1, \# \}  \\
\Gamma & = & \{ 0, 1 \} \\
F & = & \{ f \} \\
\Delta & = & \{ ((s,0,\mt), (s,0)) ((s,1,\mt), (s,1))
((s,\#,\mt), (m,\mt)) \\
& & ((m,0,\mt), (m,\mt)) ((m,1,\mt),
(m,\mt)) ((m,0,\mt), (n,\mt)) ((m,1,\mt),
(n,\mt)) \\
& & ((n,0,0), (n,\mt)) ((n,1,1), (n,\mt)) ((n,0,z_0),
(f,z_0)) ((n,1,z_0), (f,z_0)) \\
& & ((f,0,z_0), (f,z_0)) ((f,1,z_0), (f,z_0)) \} \\
\eeq

\mypage 

\prob{3: Pumping Theorem for CFLs}

\noindent Show that the following languages are not context-free. 

\subprob{a} $A = \{ ww : w \in \{0,1\}^*\}$

Basic idea: The only case in which the pumping theorem could hold is for
a parse where v and y are the same part of their respective w's.
However, the $|vxy| \leq k$ prevents this from happening since $|vxy|$
will necessarily needs to be longer than $k$ to satisfy this parse.

\noindent Assume that $A$ is context-free. So, $\exists k$ such that
$\forall w \in A$ with $|w|>k$,  $w = uvxyz$ such that $|vy| > 0$ and
$|vxy| \leq k$, $\forall n: uv^nxy^nz \in A$. 

\noindent Cases: 
\vspace*{-.15in}
\begin{enumerate}
\item v and y are in the first ``w'':  for $n \not = 1$, the first ``w''
is no longer the same as the second ``w''
\item v and y are in the second ``w'': for $n \not = 1$, the second
``w'' is no longer the same as the first ``w''
\item v is in the first ``w'' and y is in the second ``w'':  for $n \not
= 1$,  the first ``w'' is no longer the same as the second ``w''
\item v is in either the first ``w'' or the second ``w'' and y is empty:
for $n \not = 1$, the first ``w'' is no longer the same as the second
``w''  
\item y is in either the first ``w'' or the second ``w'' and x is empty:
for $n \not = 1$, the first ``w'' is no longer the same as the second
``w''
\end{enumerate}

\subprob{b} $B = \{ w\#w^R\#w : w \in \{0,1\}^*\}$

\noindent Assume $B$ is context-free. So, $\exists k$ such that $\forall
w \in B$ with $|w| > k$, $w = uvxyz$, and $|vy| > 0$, $\forall n:
uv^nxy^nz \in B$.

\noindent Cases:
\vspace*{-.15in}
\begin{enumerate}
\item v and y contain part of the first ``w'': for $n \not = 1$, the
first ``w'' is now a different string than the second ``w''
\item v and y contain part of the reversed ``w'':  for $n \not = 1$, the
reversed ``w'' is no longer the reversed version of either the first
``w'' or the second ``w''
\item v and y contain part of the second ``w'':  for $n \not = 1$, the
second ``w'' is now different than the first ``w''
\item v is part of the first ``w'' and y is part of the reversed ``w'':
for $n \not = 1$, the first and second ``w''s are no longer the same and
the reversed ``w'' doesn't match one of the ``w''s
\item v is part of the reverse ``w'' and y is part of the second ``w'':
for $n \not = 1$, the first and second ``w''s are no longer the same 
the reversed ``w'' doesn't match one of the ``w''s
\item v is part of the first ``w'' and y is part of the second ``w'':
for $n \not = 1$, the first and second ``w''s may still be the same, but
the reversed ``w'' is no longer the reversed version of either of them
\item either v or y contains a \#:  for $n \not = 1$, there are too many
(or too few, if $n=0$) \#'s
\end{enumerate}

\mypage 

\prob{4: Push-Down Automata}

$B = \{ w\#w^R\#w : w \in \{0,1\}^*\}$ is a non-CFL (as shown in 3b)
which therefore can't be accepted by a 1-pda. However, it can be
accepted by a 2-pda. Here's a general description of how a 2-pda would
operate to accept $B$:

\begin{enumerate}
\item Read input. If it is \#, then go to 2. Otherwise, push it onto
stack 1 and repeat 1. 
\item Read input. If it matches the top of stack 1, then push it onto
stack 2, pop off the top of stack 1, and repeat 2. If it is \# and stack
1 is empty, enter final state and go to 3.
\item Read input. If it matches the top of stack 2, then pop off the top
of stack 2 and repeat 3.
\end{enumerate}

\noindent Formal description of the 2-pda: $M = (K, \Sigma , \Gamma ,
\Delta , s, z_0, F)$ where

\beq
K & = & \{ s, m, f\} \\
\Sigma & = & \{ 0, 1, \# \} \\
\Gamma & = & \{ 0, 1 \} \\
F & = & \{f\} \\
\Delta & = & \{ ((s,0,\mt,\mt), (s,0,\mt)) ((s,1,\mt,\mt), (s,1,\mt))
((s,\#,\mt,\mt), (m,\mt,\mt)) \\
& & ((m,0,0,\mt), (m,\mt,0)) ((m,1,1,\mt), (m,\mt,1)) ((m,\#,z_0,\mt),
(f,z_0,\mt)) \\
& & ((f,0,\mt,0), (f,\mt,\mt)) ((f,1,\mt,1), (f,\mt,\mt)) \}
\eeq

\noindent Thus, since 2-pda's can accept non-CFLs, they are more
powerful than 1-pda's.

\mypage

\prob{5: Closure Properties}

\subprob{a} Use closure under union to show that $L = \{ w \in \{0,1\}^*
: w = w^R\}$ is context-free.

\vspace*{2in}

\subprob{b} Show that the context-free languages are closed under
reversal. 

\vspace*{2in}

\subprob{c} Give an example of a context-free language $L$ whose
complement, $\bar{L}$, is not context-free.

\vspace*{2in}

\end{document}
