\documentclass[10pt,letterpaper,unboxed,cm]{hmcpset}
\usepackage[margin=1in]{geometry}
\usepackage{graphicx, xcolor}
\usepackage{varwidth, multicol}
\pagestyle{empty}
\newcommand{\cmd}[1]{\texttt{\color{blue}{#1}}}
\newcommand{\st}{~\mid~}
\name{}
\class{CSE 105}
\assignment{Group Homework 4}
\duedate{Due: Saturday February 17, 2018 at 11:00PM (on Gradescope)}
\begin{document}
\begin{center}
\begin{minipage}[t]{5.7in}
\rule{\linewidth}{2pt}
{\sc Instructions}\newline
{\bf One member} of the group should upload your group submission to Gradescope.
During the submission process, they will be prompted to add the names of the rest
of the group members.
All group members' names and PIDs
should be on {\bf each} page of the submission.\\
Your homework must be typed. Your assignments in this class will be evaluated not only on the correctness of your answers, but on your ability to present your ideas clearly and logically. You should always explain how you arrived at your conclusions, using mathematically sound reasoning.\\
{\sc Reading} Sipser Sections 2.1, 2.2, 2.3.
\newline
{\sc Key Concepts} Pushdown automata, context-free
grammars, context-free languages, derivations, parse trees, ambiguous grammars,
leftmost derivations.
\newline
\rule{\linewidth}{2pt}
\end{minipage} \hfill
\end{center}
\problemlist{}
\begin{problem}[1.]{\bf (10 points)}
(No justifications are necessary for this problem.)
Consider the PDA over the alphabet $\{0,1\}$ given by the state diagram:
\begin{center}
\includegraphics[scale=0.3]{hw4_1}
\end{center}
\begin{itemize}
\item[a)]
Write a description in set builder notation of the language that is recognized by this PDA.
\item[b)]
Write a CFG that generates the language recognized by this PDA.
\item[c)]
Write out a left-most derivation for the string $001111000$ using your CFG from part b.
\end{itemize}
\end{problem}
\begin{problem}[2.] {\bf (10 points)}
In class we have seen that context-free languages are not closed under intersection. In this problem, we will show that if $L$ is a context-free language and $K$ is a regular language then $L\cap K$ is context-free.
\begin{itemize}
\item[a)]
Let $M_1=(Q_1,\Sigma,\Gamma,\delta_1,q_1,F_1)$ be a PDA that recognizes $L$ and $M_2 = (Q_2,\Sigma,\delta_2,q_2,F_2)$ a DFA that recognizes $K$.
Consider the construction of a PDA that recognizes $L\cap K$.
$$N=(Q_1\times Q_2,\Sigma,\Gamma,\delta,(q_1, q_2),F_1\times F_2).$$
with transition function
$$\delta((q,r),u,v)=
\left\{
\begin{array}{cr}
\{(~(\alpha,\delta_2(r,u)),\beta~)\st
(\alpha,\beta)\in \delta_1((q,u,v))\}
&~~if~~u\neq \varepsilon\\
~~\\
\{(~(\alpha,r),\beta~)\st
(\alpha,\beta)\in \delta_1((q,u,v))\}
&~~if~~u= \varepsilon
\end{array}
\right.$$
for $q\in Q_1, r\in Q_2, u\in \Sigma_\varepsilon, v\in \Gamma_\varepsilon$.
\bigskip
Apply this construction to the PDA and DFA below:
\includegraphics[scale=0.2]{hw4_2}
\includegraphics[scale=0.2]{hw4_3}
\item[b)]
Describe using set builder notation the language that is recognized by the PDA given in part a. (no justification necessary.)
\item[c)]
Describe using set builder notation the language that is recognized by the DFA given in part a. (No justification necessary.)
\item[d)]
Describe using set builder notation the language that is recognized by the PDA that is the result of the construction in part a. (You must describe it without using the intersection operation. No justification necessary.)
\end{itemize}
\end{problem}
\begin{problem}[3.] {\bf (10 points)}
\begin{itemize}
\item[a)]
Consider the true statements:
\begin{itemize}
\item
If $A$ and $B$ are regular languages then $A\cap B$ is regular.
\item
There exist context-free languages $A$ and $B$ such that $A\cap B$ is not context-free
\end{itemize}
Explain why the statement from problem 2;
\begin{center}
``If $L$ is a context-free language and $K$ is a regular language then $L\cap K$ is context-free."
\end{center}
does not contradict each of these bullet points.
\item[b)]
Find languages $A\subsetneq B\subsetneq C\subsetneq D\subsetneq E$ all over the alphabet $\{a,b,c\}$ such that:
\begin{itemize}
\item
$A$ is not context-free
\item
$B$ is context-free and non-regular
\item
$C$ is regular
\item
$D$ is non-regular
\item
$E$ is regular and not $\{a,b,c\}^*$
\end{itemize}
Briefly justify the subset inclusions and either prove or cite examples in the book to explain why you chose each set.
\end{itemize}
\end{problem}
\end{document}