\documentclass[10pt]{article}
\usepackage[margin=1in]{geometry}
\usepackage[small]{titlesec}
\usepackage{palatino, mathpazo}
\usepackage{inconsolata}
\usepackage{amsmath, amssymb}
\usepackage{enumerate}
\usepackage{graphicx}
\usepackage[normalem]{ulem}
\usepackage[mathscr]{euscript}
\usepackage{inconsolata}
\newcommand{\ds}{\displaystyle}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\LL}{\mathscr{L}}
\newcommand{\CC}{\mathscr{C}}
\newcommand{\ttt}{\texttt}
\newcommand{\Length}{\ttt{Length}}
\newcommand{\Prefix}{\ttt{Prefix}}
\newcommand{\Double}{\ttt{Double}}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.5ex}
\title{\sc Math 4931 / 5931 -- Special Topics: Theory of Computation and Formal Languages\\[10pt]Homework 2}
\author{
Spring 2023\\[10pt]
due Wednesday, February 22, \underline{by the beginning of class}
}
\date{}
\begin{document}
\maketitle
\begin{center}
\emph{This homework assignment was written in \LaTeX{}. You can find the source code on the course website.}
\end{center}
\textbf{\underline{You must explain your reasoning for all of your answers. Correct answers with no justification or}\\[5pt]\underline{explanation will not be accepted.}}
\textbf{Students enrolled in Math 4931: Complete any 6 out of the 9 problems.}\\
\textbf{Students enrolled in MSSC 5931: Complete any 8 out of the 9 problems.}\\
\begin{enumerate}
\item Find a DFA for the language $\{w \in \{a,b\}^* : w \not \in (a^* \cup b^*)\}$. Draw the diagram of the DFA and give the full formal definition.
\item During the proof that the set of recognizable languages is closed under union, we noted that setting the accept states $F = F_1 \times F_2$ forms a DFA for the intersection of two languages. Define $\LL = \{w \in \{a,b\}^* : \text{$w$ has at least three $a$'s and at least two $b$'s}\}$. Describe $\LL$ as the intersection of two simpler languages, find DFAs for each of them, and use the intersection construction to derive a DFA for $\LL$. Draw the diagram of the DFA and give the full formal definition.
\item \begin{enumerate}
\item Find a DFA for the language $\{w \in \{0,1\}^* : \text{$w$ has length at least $3$ and its third symbol is a $0$}\}$. Draw the diagram and give the full formal definition.
\item Define $\LL_n = \{w \in \{0,1\}^* : \text{$w$ has length at least $n$ and its $n$th symbol is a $0$}\}$. Give the formal definition for a DFA for $\LL_n$.
\end{enumerate}
\item Let $\Sigma = \{a,b\}$. For $k \geq 1$, let $\CC_k$ be the language consisting of all strings that contain an $a$ exactly $k$ places from the right-hand end. Prove that for each $k$, no DFA can recognize $\CC_k$ with fewer than $2^k$ states.
\item Let $\LL_1$ and $\LL_2$ be recognizable languages. Define the \emph{perfect shuffle} of $\LL_1$ and $\LL_2$ to be the words you get by interleaving equal length words from each:
\[
\{w : w = u_1v_1u_2v_2\cdots u_kv_k,\text{ where $u_1\ldots u_k \in \LL_1$ and $v_1 \ldots v_k \in \LL_2$ }\}.
\]
Prove that if $\LL_1$ and $\LL_2$ are recognizable, then so is their \emph{perfect shuffle}.
\item In certain programming languages, comments appear between delimiters such as \ttt{/\#} and \ttt{\#/}. Let $\CC$ be the language of all valid delimited comment strings. A member of $\CC$ must begin with \ttt{/\#} and end with \ttt{\#/} but have no intervening \ttt{\#/}. For simplicity, assume the alphabet for $\CC$ is $\{a, b, /, \#\}$. So, for example
\[
/\# abbaa/ba\#a/\#ba\#/ \in \CC \qquad\qquad \text{ but } \qquad\qquad /\# abba\#/abcs\#/ \not\in \CC.
\]
\begin{enumerate}
\item Give a DFA that recognizes $\CC$. A diagram will suffice, you do not need to give the formal definition.
\item Give a regular expression that matches $\CC$.
\end{enumerate}
\item Recall from Homework 1 that $\LL^R$ is the language of all words from $\LL$, but reversed. There is a theorem (that we need NFAs to prove) that if $\LL$ is recognizable by a DFA then so is $\LL^R$. However, even without NFAs, it's possible to demonstrate that a DFA for $\LL^R$ could end up with exponentially more states that a DFA for $\LL$. Give a convincing example of this. (To be the most convincing, you should come up with a family of languages $\LL_k$ such that the number of states of $\LL_1^R$, $\LL_2^R$, $\LL_3^R$, etc grows exponentially fast relative to the number of states of $\LL_1$, $\LL_2$, $\LL_3$, $\ldots$.)
% Easter Egg! This will actually be on homework 3.
% \item For any language $\LL$, define
% \[
% \Length(\LL) = \{w \in 0^* : |w| = |v| \text{ for some $v \in \LL$}\}.
% \]
% Prove that if $\LL$ is recognizable than so is $\Length(\LL)$.
\item For any language $\LL$, define
\[
\Prefix(\LL) = \{u : uv \in \LL \text{ for some $v \in \Sigma^*$}\}.
\]
Prove that if $\LL$ is recognizable then so is $\Prefix(\LL)$.
\item For any word $w = w_1w_2 \cdots w_n$, define $\Double(w) = w_1w_1w_2w_2\cdots w_nw_n$. For a language $\LL$, define $\Double(\LL) = \{\Double(w) : w \in \LL\}$. Assume that $\LL$ is recognizable, and find a DFA for $\Double(\LL)$. Make sure to give a full formal definition.
\end{enumerate}
\end{document}