% 
% LaTeX Problem Set Template by Sachin Padmanabhan
% I created this when I was a freshman in CS 103,
% and I continue to use it to this day.
%
% Hope you enjoy!
%
% There may be problems with this template.
% If so, feel free to contact me.
%

% Update for Fall 2018 by Michael Zhu
% Updated for Fall 2019 by Joshua Spayd

\documentclass{article}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{mathdots}
\usepackage[pdftex]{graphicx}
\usepackage{fancyhdr}
\usepackage[margin=1in]{geometry}
\usepackage{multicol}
\usepackage{bm}
\usepackage{listings}
\PassOptionsToPackage{usenames,dvipsnames}{color}  %% Allow color names
\usepackage{pdfpages}
\usepackage{algpseudocode}
\usepackage{tikz}
\usetikzlibrary{automata,positioning}
\usepackage{enumitem}
\usepackage[T1]{fontenc}
\usepackage{inconsolata}
\usepackage{framed}
\usepackage{wasysym}
\usepackage[thinlines]{easytable}
\usepackage{wrapfig}
\usepackage[hidelinks]{hyperref}
\usepackage{mathrsfs}
\usepackage{tabularx} % also loads 'array' package
\newcolumntype{C}{>{\centering\arraybackslash}X} % centered version of 'X' columns
\usepackage{diagbox}
\usepackage{colortbl}
\usepackage{fourier}
\usepackage{makecell}

\title{CS 103: Mathematical Foundations of Computing\\Problem Set \#7}
\author{Your Name(s) Here}
\date{\today}

% Running author based on https://tex.stackexchange.com/a/68310
\makeatletter
\let\runauthor\@author
\makeatother

\lhead{\runauthor}
\chead{Problem Set \#7}
\rhead{\today}
\lfoot{}
\cfoot{CS 103: Mathematical Foundations of Computing --- Autumn 2019}
\rfoot{\thepage}

\newcommand{\abs}[1]{\lvert #1 \rvert}
\newcommand{\absfit}[1]{\left\lvert #1 \right\rvert}
\newcommand{\norm}[1]{\left\lVert #1 \right\rVert}
\newcommand{\eval}[3]{\left[#1\right]_{#2}^{#3}}
\renewcommand{\(}{\left(}
\renewcommand{\)}{\right)}
\newcommand{\floor}[1]{\left\lfloor#1\right\rfloor}
\newcommand{\ceil}[1]{\left\lceil#1\right\rceil}
\newcommand{\pd}[1]{\frac{\partial}{\partial #1}}
\newcommand{\inner}[1]{\langle#1\rangle}
\newcommand{\cond}{\bigg|}
\newcommand{\rank}[1]{\mathbf{rank}(#1)}
\newcommand{\range}[1]{\mathbf{range}(#1)}
\newcommand{\nullsp}[1]{\mathbf{null}(#1)}
\newcommand{\repr}[1]{\left\langle#1\right\rangle}
\newcommand\VRule[1][\arrayrulewidth]{\vrule width #1}

\DeclareMathOperator{\Var}{Var}
\DeclareMathOperator{\tr}{tr}
\DeclareMathOperator{\Tr}{\mathbf{Tr}}
\DeclareMathOperator{\diag}{\mathbf{diag}}
\DeclareMathOperator{\dist}{\mathbf{dist}}
\DeclareMathOperator{\prob}{\mathbf{prob}}
\DeclareMathOperator{\dom}{\mathbf{dom}}
\DeclareMathOperator{\E}{\mathbf{E}}
\DeclareMathOperator{\Q}{\mathbb{Q}}
\DeclareMathOperator{\R}{\mathbb{R}}
\DeclareMathOperator{\var}{\mathbf{var}}
\DeclareMathOperator{\quartile}{\mathbf{quartile}}
\DeclareMathOperator{\conv}{\mathbf{conv}}
\DeclareMathOperator{\VC}{VC}
\DeclareMathOperator*{\argmax}{arg\,max}
\DeclareMathOperator*{\argmin}{arg\,min}
\DeclareMathOperator{\Ber}{Bernoulli}
\DeclareMathOperator{\NP}{\mathbf{NP}}
\DeclareMathOperator{\coNP}{\mathbf{coNP}}
\DeclareMathOperator{\TIME}{\mathsf{TIME}}
\DeclareMathOperator{\polytime}{\mathbf{P}}
\DeclareMathOperator{\PH}{\mathbf{PH}}
\DeclareMathOperator{\SIZE}{\mathbf{SIZE}}
\DeclareMathOperator{\ATIME}{\mathbf{ATIME}}
\DeclareMathOperator{\SPACE}{\mathbf{SPACE}}
\DeclareMathOperator{\ASPACE}{\mathbf{ASPACE}}
\DeclareMathOperator{\NSPACE}{\mathbf{NSPACE}}
\DeclareMathOperator{\Z}{\mathbb{Z}}
\DeclareMathOperator{\N}{\mathbb{N}}
\DeclareMathOperator{\EXP}{\mathbf{EXP}}
\DeclareMathOperator{\NEXP}{\mathbf{NEXP}}
\DeclareMathOperator{\NTIME}{\mathbf{NTIME}}
\DeclareMathOperator{\DTIME}{\mathbf{DTIME}}
\DeclareMathOperator{\poly}{poly}
\DeclareMathOperator{\BPP}{\mathbf{BPP}}
\DeclareMathOperator{\ZPP}{\mathbf{ZPP}}
\DeclareMathOperator{\RP}{\mathbf{RP}}
\DeclareMathOperator{\coRP}{\mathbf{coRP}}
\DeclareMathOperator{\BPL}{\mathbf{BPL}}
\DeclareMathOperator{\IP}{\mathbf{IP}}
\DeclareMathOperator{\PSPACE}{\mathbf{PSPACE}}
\DeclareMathOperator{\NPSPACE}{\mathbf{NPSPACE}}
\DeclareMathOperator{\SAT}{\mathsf{SAT}}
\DeclareMathOperator{\NL}{\mathbf{NL}}
\DeclareMathOperator{\PCP}{\mathbf{PCP}}
\DeclareMathOperator{\PP}{\mathbf{PP}}
\DeclareMathOperator{\cost}{cost}
\let\Pr\relax
\DeclareMathOperator*{\Pr}{\mathbf{Pr}}

\definecolor{shadecolor}{gray}{0.9}

\theoremstyle{plain}
\newtheorem*{lem}{Lemma}

\theoremstyle{plain}
\newtheorem*{claim}{Claim}

\newtheorem{theorem}{Theorem}[section]
\newtheorem*{thm}{Theorem}
\newtheorem*{fthm}{Theorem (Formalized)}
\newtheorem{corollary}{Corollary}[theorem]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem*{wrongthm}{(Incorrect!) Theorem}

\newenvironment{wrongproof}{
  \setlength{\parskip}{6pt}
  \paragraph{\it{(Incorrect!) Proof.}}}
  {\hfill\qedsymbol}

\newenvironment{incorrect}{
  \begin{tabular}{m{.25in}|m{\linewidth-.5in-6\tabcolsep}|m{.25in}}
    \arrayrulecolor{incorrect}\cline{2-2}
    \makecell[c]{\textcolor{incorrect}{\danger}} &
    \vspace{\baselineskip}
}{
    ~\newline &
    \makecell[c]{\textcolor{incorrect}{\danger}} \\
    \arrayrulecolor{incorrect}\cline{2-2}
  \end{tabular}
}


\renewcommand{\headrulewidth}{0.4pt}
\renewcommand{\footrulewidth}{0.4pt}

\setlength{\parskip}{6pt}
\setlength{\parindent}{0pt}
\setenumerate{topsep=0pt}
\setlist{topsep=0pt}

\pagestyle{fancy}

\renewcommand{\thefootnote}{\fnsymbol{footnote}}

\definecolor{incorrect}{RGB}{182,0,12}

% start MZ
\usetikzlibrary{automata,positioning}
\let\oldemptyset\emptyset
\renewcommand{\emptyset}{\text{\O}}
\renewcommand\qedsymbol{$\blacksquare$}
\newenvironment{prf}{{\bfseries Proof.}}{\qedsymbol}
\renewcommand{\emph}[1]{\textit{\textbf{#1}}}
\newcommand{\annotate}[1]{\textit{\textcolor{blue}{#1}}}
\usepackage{stmaryrd}
\usepackage{minted}
\usepackage{mathtools}
\usepackage{alltt}
\newcommand{\ttt}[1]{\texttt{#1}}
\newcommand{\match}[1]{\textbf{\underline{#1}}}
\usepackage{parskip}
\newcommand{\lcurly}{\textbf{\ttt{\{}}}
\newcommand{\rcurly}{\textbf{\ttt{\}}}}

% end MZ

\begin{document}

\maketitle{\vspace{-1.0cm}}

\section{Designing Regular Expressions}

Below are a list of alphabets and languages over those alphabets. For each
language, write a regular expression for that language. \emph{Please use our
online tool to design, test, and submit your regular expressions. Typed or
handwritten solutions will not be accepted.} To use it, visit the CS103 website
and click the ``Regex Editor'' link under the ``Resources'' header. If you
submit in a pair, please tell us in your GradeScope submission who submitted
your answers to this question. Also, as a reminder, please test your
submissions thoroughly, since we'll be grading them with an autograder.

\begin{enumerate}[label*=\roman*.,ref=(\roman*)]
  \item Let $\Sigma = \{\ttt{a}, \ttt{b}, \ttt{c}, \ttt{d}, \ttt{e}\}$. Write a
    regular expression for the language $\{w \in \Sigma^* \mid $ the letters in
    $w$ are sorted alphabetically\}. For example, $\ttt{abcde} \in L$,
    $\ttt{bee} \in L$, $\ttt{a} \in L$ and $\varepsilon \in L$, but
    $\ttt{decade} \not\in L$.

  \item Write a regular expression for the complement of the language from part
    (i) of this problem.

  \annotate{As with NFAs, there's no simple way to start with a regex for a
    language $L$ and to turn it into a regex for $\overline{L}$.}

  \item On Unix-style operating systems like macOS or Linux, files are
    organized into directories. You can reference a file by giving a
    \textit{path} to the file, a series of directory names separated by
    slashes. For example, the path \ttt{/home/username/} might represent a
    user's home directory, and a path like
    \ttt{/home/username/Documents/PS7.tex} might represent that person's
    solution to this problem set. Paths that start with a slash character are
    called \textit{absolute paths} and say exactly where the file is on disk.
    Paths that don't start with a slash are called \textit{relative paths} and
    say where, relative to the current folder, a file can be found. For
    example, if I'm logged into my computer and am in my home folder, I could
    look up the file \ttt{Documents/PS7.tex} to find my solution to this
    problem set.

    The general pattern here is that a file path consists of a series of
    directory or file names separated by slashes. That path might optionally
    start with a slash, but isn't required to, and it might option- ally end
    with a slash, but isn't required to. However, you can't have two
    consecutive slashes.\footnote{In some cases you technically \textit{can}
    have multiple consecutive slashes, but we'll ignore that for now.}

    Let $\Sigma = \{\ttt{a},\ttt{/\}}$. Write a regular expression for $L = \{w
    \in \Sigma^* \mid w$ represents the name of a file path on a Unix-style
    system \}. For example, $\ttt{/aaa/a/aa} \in L$, $\ttt{/} \in L$, $\ttt{a}
    \in L$, $\ttt{/a/a/a/} \in L$, and $\ttt{aaa/} \in L$, but $\ttt{//a//}
    \notin L$, $\ttt{a//a} \notin L$, and $\varepsilon \notin L$.

    Fun fact: this problem comes from former CS103 instructor Amy Liu, who
    fixed a bug in industrial code that arose when someone wrote the wrong
    regex for this language. Oops.

  \item Suppose you are taking a walk with your dog on a leash of length two.
    Let $\Sigma = \{\ttt{y}, \ttt{d}\}$ and let  $L = \{w \in \Sigma^* \mid w$
    represents a walk with your dog on a leash where you and your dog both end
    up at the same location\}. For example, we have $\ttt{yyddddyy} \in L$
    because you and your dog are never more than two steps apart and both of
    you end up four steps ahead of where you started; similarly, $\ttt{ddydyy}
    \in L$. However, $\ttt{yyyyddd} \notin L$, since halfway through your walk
    you're three steps ahead of your dog; $\ttt{ddyd} \notin L$, because your
    dog ends up two steps ahead of you; and $\ttt{ddyddyyy} \notin L$, because
    at one point your dog is three steps ahead of you. Write a regular
    expression for $L$.

  \annotate{Note that, unlike Problem Set Six, you and your dog \textbf{must}
    end at the same position.}

  \item Let $\Sigma = \{\texttt{M, D, C, L, X, V, I}\}$ and let $L = \{w \in
    \Sigma^* \mid w$ is number less than 2,000 represented in Roman numerals\}.
    For example, $\texttt{CMXCIX} \in L$, since it represents the number 999,
    as are the strings \ttt{L} (50), \ttt{VIII} (8), \ttt{DCLXVI} (666),
    \ttt{CXXXVII} (137), \ttt{CDXII} (412), and \ttt{MDCXVIII} (1,618).
    However, we have $\ttt{VIIII} \notin L$ (you'll never have four \ttt{I}'s
    in a row; use \ttt{IX} or \ttt{IV} instead), that $\ttt{MM} \notin L$ (it's
    a Roman numeral, but it's for 2,000, which is too large), that $\ttt{VX}
    \notin L$ (this isn't a valid Roman numeral), and that $\ttt{IM} \not\in L$
    (the notation of using a smaller digit to subtract from a larger one only
    lets you use \ttt{I} to prefix \ttt{V} and \ttt{X}, or \ttt{X} to prefix
    \ttt{L} and \ttt{C}, or \ttt{C} to prefix \ttt{D} and \ttt{M}). The Romans
    didn't have a way of expressing the number 0, so to make your life easier
    we'll say that $\varepsilon \in L$ and that the empty string represents 0.
    (Oh, those silly Romans.) Write a regular expression for $L$. 

    (As a note, we're using the ``standard form'' of Roman numerals. You can
    see a sample of numbers written out this way via
    \href{http://literacy.kent.edu/Minigrants/Cinci/romanchart.htm}
    {\textcolor{blue}{\underline{this link}}}.)
\end{enumerate}
\begin{shaded}
  Write the SUNetID of the person who submitted the regular expressions here. 
\end{shaded}

\pagebreak

\section{Finite Languages}

A language $L$ is called \emph{finite} if $L$ contains finitely many strings
(that is, $|L|$ is a natural number).

Given a finite language $L$, explain how to write a regular expression for $L$.
Briefly justify your answer; no formal proof is necessary. This shows that all
finite languages are regular.

\annotate{Watch for edge cases!}

\begin{shaded}
  Write your answer here.
\end{shaded}

\pagebreak

\section{State Elimination}

The state elimination algorithm gives a way to transform a finite automaton a
DFA or NFA into a regular expression. It's a really beautiful algorithm once
you get the hang of it.

Let $\Sigma = \{\ttt{a}, \ttt{b}\}$ and let $L = \{w \in \Sigma^* \mid w$ has
an even number of \ttt{a}'s and an even number of \ttt{b}'s\}. Below is a
finite automaton for $L$ that we've prepared for the state elimination
algorithm by adding in a new start state $q_{\text{start}}$ and a new accept
state $q_{\text{acc}}$:

\begin{center}
\tikzstyle{accepting}=[double distance=2pt, outer sep=1pt+\pgflinewidth]
\begin{tikzpicture}[shorten >=1pt,node distance=2.2cm,on grid,auto,
    state/.style={circle, draw, minimum size=1.1cm}]
  % \node[state, options?] (identifier) [placement] {node label};
  \node[state, initial] (s) {$q_{\text{start}}$};
  \node[state] (0) [right=of s] {$q_0$};
  \node[state] (1) [right=of 0] {$q_1$};
  \node[state, accepting] (a) [above=of 0] {$q_{\text{acc}}$};
  \node[state] (2) [below=of 0] {$q_2$};
  \node[state] (3) [below=of 1] {$q_3$};

  % (start identifier) edge [options?] node {edge label} (target identifier)
  %                    edge [options?] node {edge label} (another target
  %                                                       identifier)
  \path[->]
  (s) edge node {$\varepsilon$} (0)
  (0) edge [bend left=10] node {$a$} (1)
      edge node {$\varepsilon$} (a)
      edge [bend left=10] node {$b$} (2)
  (1) edge [bend left=10] node {$a$} (0)
      edge [bend left=10] node {$b$} (3)
  (2) edge [bend left=10] node {$b$} (0)
      edge [bend left=10] node {$a$} (3)
  (3) edge [bend left=10] node {$b$} (1)
      edge [bend left=10] node {$a$} (2);
\end{tikzpicture}
\end{center}

We'd like you to use the state elimination algorithm to produce a regular
expression for $L$.

\begin{center}
  \annotate{(Continued on the next page)}
\end{center}

\pagebreak

\begin{enumerate}[label*=\roman*.,ref=(\roman*)]
  \item Run two steps of the state elimination algorithm on the above
    automaton. Specifically, first remove state $q_1$, then remove state $q_2$.
    Show your result at this point.

    \annotate{Remember that to eliminate a state $q$, you should identify all
    pairs of states $q_{in}$ and $q_{out}$ where there's a transition from
    $q_{in}$ to $q$ and from $q$ to $q_{out}$, then add shortcut edges from
    $q_{in}$ to $q_{out}$ to bypass state $q$. Remember that $q_{in}$ and
    $q_{out}$ may be the same state. To help you check your work: there are
    four such pairs for state $q_1$.}

    \annotate{If you've done everything properly, at the end of this stage, no
    transitions in your automaton should have Kleene stars in them.}

    \begin{shaded}
      Provide the resulting automaton here.
      % You can copy and modify the above automaton drawn using the tikz
      % automata package, or use a finite automata editor such as
      % http://madebyevan.com/fsm/ If you choose to draw and then scan/take a
      % picture, *please* make sure that the image is clearly legible in
      % Gradescope!
    \end{shaded}

    \pagebreak

  \item \label{p:elim} Finish the state elimination algorithm by first
    eliminating $q_3$, then $q_0$. Show your result.

    \annotate{This is where you'll start seeing Kleene stars.}

    \begin{shaded}
      Provide the resulting automaton here.
    \end{shaded}

    \pagebreak

  \item Submit your resulting regular expression through our regular expression
    tool along the lines of what you did in Problem One. If you're working in a
    pair, tell us on GradeScope who submitted it.

    \annotate{Not sure whether you have the right answer? \textbf{Test your
    result thoroughly!}}

    \begin{shaded}
      Write the SUNetID of the person who submitted the regular expression here.
    \end{shaded}
\end{enumerate}

Something we strongly recommend: look at the regular expression you ended up
with in part \ref{p:elim} of this problem. How does it work? That is, how does
that regular expression match all and only strings with an even number of
\ttt{a}'s and an even number of \ttt{b}'s? The particular mechanism it uses is
quite clever, and it's amazing that something that sophisticated dropped out of
a mechanical transformation on a DFA! You don't need to submit an answer to
this question, but you should aim to have a rock-solid understanding.

\pagebreak

\section{At Least Three Point Five}

The Myhill-Nerode theorem is a powerful tool for finding nonregular languages,
but it can take some adjusting to get used to.

Let $\Sigma = \{\ttt{a}, \ttt{b}\}$ and consider the following language:
\begin{equation*}
  L = \{w \in \Sigma^* \mid \text{there are at least as many \ttt{a}'s as
  \ttt{b}'s in }w\}.
\end{equation*}
This language $L$ isn't regular; make sure you have an intuition for why this
is.

Below is an attempted proof that $L$ isn't regular. Although the claim it's
proving is indeed true, this proof contains an error that renders it incorrect.

\begin{incorrect}
  \begin{thm}
    $L$ is not a regular language.
  \end{thm}
  \begin{wrongproof}
    Consider the set $S = \{ \ttt{a}^n\ |\ n \in \N \}$. We will prove that $S$
    is infinite and that $S$ is a distinguishing set for $L$.

    To see that $S$ is infinite, note that it contains one string for each
    natural number.

    To see that $S$ is a distinguishing set for $L$, consider any distinct
    strings $\ttt{a}^m, \ttt{a}^n \in S$, and assume without loss of generality
    that $m > n$. Then $\ttt{b}^m\ttt{a}^m \in L$ because this string contains
    the same number of \ttt{a}'s and \ttt{b}'s, but $\ttt{b}^m\ttt{a}^n \notin
    L$ because it contains $m$ \ttt{b}'s and $n$ \ttt{a}'s and $m > n$.
    Therefore, we see that $\ttt{a}^m \not\equiv_L \ttt{a}^n$.

    Because $S$ is a distinguishing set for $L$ that contains infinitely many
    strings, by the Myhill-Nerode theorem we see that $L$ is not regular.
  \end{wrongproof}
\end{incorrect}

Alas, this proof contains an error.

\begin{enumerate}[label=\roman*.,ref=(\roman*)]
  \item What's wrong with this proof? Be as specific as possible.

    \annotate{The best way to identify a flaw in a proof is to point to a
    specific claim that's being made that's not true or not properly
    substantiated and to explain why.}

    \begin{shaded}
      Write your answer here.
    \end{shaded}
\end{enumerate}

\pagebreak

Here's another attempt at a proof that L isn’t regular:

\begin{incorrect}
  \begin{thm}
    $L$ is not a regular language.
  \end{thm}
  \begin{wrongproof}
    Consider the set $S = \{ \ttt{a}^n\ |\ n \in \N \}$. We will prove that $S$
    is infinite and that $S$ is a distinguishing set for $L$.

    To see that $S$ is infinite, note that it contains one string for each
    natural number.

    To see that $S$ is a distinguishing set for $L$, consider any distinct
    strings $\ttt{a}^n, \ttt{a}^{n+1} \in S$. Then $\ttt{a}^{n+1}\ttt{b}^{n+1}
    \in L$ because this string contains the same number of \ttt{a}'s and
    \ttt{b}'s, but $\ttt{a}^n\ttt{b}^{n+1} \notin L$ because it contains $n+1$
    \ttt{b}'s but only $n$ \texttt{a}'s. Therefore, we see that $\ttt{a}^{n+1}
    \not\equiv_L \ttt{a}^n$.

    Because $S$ is a distinguishing set for $L$ that contains infinitely many
    strings, by the Myhill-Nerode theorem we see that $L$ is not regular.
  \end{wrongproof}
\end{incorrect}

Sadly, this proof is also wrong:

\begin{enumerate}[resume*]
  \item What's wrong with this proof? Be as specific as possible.

    \annotate{Fun fact: the error in this proof is one of the most common
    mistakes we see people make in Myhill-Nerode proofs.}

    \begin{shaded}
      Write your answer here.
    \end{shaded}
\end{enumerate}

\pagebreak

\section{Embracing the Braces}

Let $\Sigma$ be an alphabet containing two characters, the open curly brace
character \lcurly and the close curly brace character \rcurly. Consider the
following language over $\Sigma$:
\begin{equation*}
  L_1 = \{w \in \Sigma^* \mid w\text{ is a string of balanced curly braces}\}
\end{equation*}
For example, we have $\lcurly\rcurly \in L_1$, $\lcurly\lcurly\rcurly\rcurly
\in L_1$, $\lcurly\lcurly\rcurly\lcurly\rcurly\rcurly\lcurly\rcurly \in L_1$,
$\varepsilon \in L_1$, and
$\lcurly\lcurly\rcurly\rcurly\lcurly\lcurly\lcurly\rcurly\lcurly\rcurly\rcurly
\rcurly \in L_1$, but $\rcurly\lcurly\ \not\in L_1$, $\lcurly\lcurly\rcurly
\not\in L_1$, and $\lcurly\rcurly\rcurly\rcurly \not\in
L_1$. This question explores properties of this language.

\begin{enumerate}[label*=\roman*.,ref=(\roman*)]
  \item \label{p:curlynonreg} Prove that $L_1$ is not a regular language. One
    consequence of this result -- which you don't need to prove -- is that
    real-world languages that support some sort of nested structures, such as
    most programming languages and HTML, aren't regular and so can't be parsed
    using regular expressions.

    \annotate{As a first step, ask yourself: if you were reading an input
    string from left to right, what information would you have to keep track
    of? The Myhill-Nerode theorem asks you to find a distinguishing set of
    infinite size. Based on that, find two distinguishable strings by finding
    two strings that have different ``information'' associated with them,
    where, here, ``information'' corresponds to what you found in the first
    step.}

    \annotate{Once you've done that, find a third string distinguishable from
    the previous two strings. It should correspond to some different piece of
    ``information.'' Once you've done this, keep adding in more strings until
    you've spotted a pattern that lets you define an infinite distinguishing
    set.}

    \begin{shaded}
      Provide a proof here.
    \end{shaded}
\end{enumerate}

\pagebreak

Let's say that the \emph{nesting depth} of a string of balanced parentheses is
the maximum number of unmatched open parentheses at any point inside the
string. For example, the string
\lcurly\lcurly\rcurly\lcurly\lcurly\rcurly\rcurly\rcurly\ has nesting depth
three, the string \lcurly\lcurly\rcurly\lcurly\rcurly\rcurly\lcurly\rcurly\ has
nesting depth two, and the string $\varepsilon$ has nesting depth zero.

Consider the language $L_2 = \{w \in \Sigma^* \mid w$ is a string of balanced
curly braces with nesting depth at most 4\}. For example, $\lcurly\rcurly \in
L_2$, $\lcurly\lcurly\rcurly\lcurly\rcurly\rcurly \in L_2$, and
$\lcurly\lcurly\lcurly\lcurly\rcurly\rcurly\rcurly\rcurly\lcurly\lcurly\rcurly
\rcurly \in L_2$, but
$\lcurly\lcurly\lcurly\lcurly\lcurly\rcurly\rcurly\rcurly\rcurly\rcurly \notin
L_2$ because although it's a string of balanced curly braces, the nesting goes
five levels deep.

\begin{enumerate}[resume*]
  \item Design a DFA for $L_2$, showing that $L_2$ is regular. A consequence of
    \textit{this} result is that while you can't parse all programs or HTML
    with regular expressions, you can parse programs with low nesting depth or
    HTML documents without deeply-nested tags using regexes. \emph{Please
    submit this DFA using the DFA editor on the course website} and tell us on
    GradeScope who submitted it.

    \begin{shaded}
      Write the SUNetID of the person who submitted the DFA here.
    \end{shaded}

    \pagebreak

  \item Look back at your proof from part \ref{p:curlynonreg} of this problem.
    Imagine that you were to take that exact proof and blindly replace every
    instance of ``$L_1$'' with ``$L_2$.'' This would give you a (incorrect)
    proof that $L_2$ is nonregular (which we know has to be wrong because $L_2$
    is indeed regular.) Where would the error be in that proof? Be as specific
    as possible.

  \annotate{Again, you should be able to point at a specific spot in the proof
    that contains a logic error and explain exactly why the statement in
    question is not true or not supported by the preceding statements. If you
    can't do this, it likely means you have an error in your proof from part
    \ref{p:curlynonreg}!}

    \begin{shaded}
      Provide an answer here.
    \end{shaded}
\end{enumerate}

Intuitively, regular languages correspond to problems that can be solved using
only finite memory. Make sure you understand why, given that intuition, $L_1$
``ought to'' be nonregular while $L_2$ ``ought to be'' regular. This sort of
intuition will be extremely helpful going forward.

\pagebreak

\section{State Lower Bounds}

The Myhill-Nerode theorem we proved in lecture is actually a special case of a
more general theorem about regular languages. This problem explores how to
generalize that result.

\begin{enumerate}[label*=\roman*.,ref=(\roman*)]
  \item \label{p:lowbound} Let $L$ be a language over $\Sigma$ and let $S$ be a
    distinguishing set for $L$. Prove that if $S$ is finite (that is, $|S|$ is
    a natual number), then any DFA for $L$ must have at least $|S|$ states.
    (You sometimes hear this referred to as \emph{lower-bounding} the size of
    any DFA for $L$.)

    \begin{shaded}
      Provide a proof here.
    \end{shaded}
\end{enumerate}

\pagebreak

\annotate{The next problem on this problem set talks about writing proofs like
these using the formal 5-tuple definition of a DFA. We are not expecting you to
do this here; feel free to structure your proof for this part of the problem
along the lines of the proofs on DFAs that you saw in lecture.}

According to old-school Twitter rules, all tweets need to be 140 characters or
less. Let $\Sigma$ be the alphabet of characters that can legally appear in a
tweet (which includes most scripts from most parts of the world, plus things
like emojis, mathematical symbols, etc.). Then, consider the following
language:
\begin{equation*}
  \textit{TWEETS} = \{w \in \Sigma^* \mid |w| \leq 140\}.
\end{equation*}
This is the language of all legal tweets, assuming the empty string is a legal
tweet. (We'll count the empty string as a legal tweet for the purposes of this
problem. Many tweets would be improved by replacing them with the empty
string.) The good news is that this language is regular. The bad news is that
any DFA for it has to be pretty large.

\begin{enumerate}[resume*]
  \item \label{p:tweet} Using your result from part \ref{p:lowbound}, prove
    that any DFA for \textit{TWEETS} must have at least 142 states.

    \annotate{It might be easier to tackle this problem if you consider
    replacing 140 and 142 with some smaller numbers (say, 2 and 4) to build up
    an intuition. And work backwards -- what will you need to do to invoke part
    \ref{p:lowbound}?}

    \begin{shaded}
      Provide a proof here.
    \end{shaded}

    \pagebreak

  \item \label{p:tweetdfa} Define a 142-state DFA for \textit{TWEETS} using the
    formal 5-tuple definition of a DFA. Briefly explain how your DFA works. No
    formal proof is necessary.

    \annotate{Again, this might be a lot easier to do if you first reduce 140
    and 142 to 2 and 4, respectively, and see what you come up with. Start by
    drawing out what the DFA would look like, then think about how you'd
    formalize your idea as a 5-tuple.}

    \annotate{As with the 5-tuple question from Problem Set Six, please define
    your transition function $\delta$ by writing out an expression of the form
    $\delta(q, a) = \rule{3em}{0.5pt}$, filling in the blank appropriately. Feel free
    to use piecewise functions, like you did on Problem One of PS4.}

    \begin{shaded}
      Provide an answer here.
    \end{shaded}
\end{enumerate}

Your results from parts \ref{p:tweet} and \ref{p:tweetdfa} collectively
establish that the smallest possible DFA for \textit{TWEETS} has exactly 142
states. This approach to finding the smallest object of some type -- using some
theorem to prove a lower bound (``we need at least this many states'') combined
with a specific object of the given type (``we certainly can't do worse than
this'') is a common strategy in algorithm design and computational complexity
theory. If you take classes like CS161, CS254, etc., you'll likely see similar
sorts of approaches!

\pagebreak

\section{The Extended Transition Function}

As you saw on Problem Set Six, formally speaking, a DFA is a 5-tuple $(Q,
\Sigma, \delta, q_0, F)$. You used the 5-tuple definition to pin down edge
cases of DFAs. But we can also use this formal definition to rigorously define
concepts about automata that, at this point, we've only discussed at a
high-level.

Let $D = (Q, \Sigma, \delta, q_0, F)$ be a DFA. We're going to define a
function $\delta^* : \Sigma^* \rightarrow Q$ called the \emph{extended
transition function of D}. Intuitively, the function $\delta^*$ takes as input
a string and outputs what state that string would end up in if run through the
DFA $D$. The function $\delta^*$ is defined, recursively, as follows:
\begin{itemize}
  \item \emph{Base case}: $\delta^*(\varepsilon) = q_0$.
  \item \emph{Recursive case}: If $w \in \Sigma^*$ and $a \in \Sigma$, then
    $\delta^*(wa) = \delta(\delta^*(w), a)$.
\end{itemize}
That's quite a mouthful, but there's a nice explanation for what's going on
here.

\begin{enumerate}[label=\roman*.,ref=(\roman*)]
  \item Explain $\delta^*$'s base case in plain English and why that makes
    sense given what $\delta^*$ represents.  Then, explain $\delta^*$'s
    recursive case in plain English and why that makes sense given what
    $\delta^*$ represents.

    \annotate{The notation here is dense, so proceed slowly. What's the input
    to the function $\delta^*$ in this case? What are w and a? You may want to
    draw out an actual DFA and try expanding out $\delta^*$ for a couple of
    strings.}

    \begin{shaded}
      Write your answer here.
    \end{shaded}

    \pagebreak

  \item Formally speaking, we can define $\mathscr{L}(D) = \{ w \in \Sigma^*
    \mid \delta^*(w) \in F \}$. Explain how this mathematical definition
    accords with the plain English one we’ve been using thus far.

    \annotate{That's a lot of symbols! Write out what each of them mean.}

    \begin{shaded}
      Write your answer here.
    \end{shaded}

    \pagebreak

  \item \label{p:samestate} Let $D = (Q, \Sigma, \delta, q_0, F)$ be a DFA, and
    let $x, y \in \Sigma^*$ be two strings where $\delta^*(x)=\delta^*(y)$.
    Prove that, for any string $z \in \Sigma^*$, we have $\delta^*(xz) =
    \delta^*(yz)$.

    \annotate{Your proof will need to rely on the definition of $\delta^*$.
    Since $\delta^*$ is defined recursively, what style of proof do you think
    you might want to use here?}

    \annotate{We are expecting you to write a formal proof here that uses the
    definition of the $\delta^*$ function. As you're reasoning through why this
    result is true, feel free to think at a high level about ideas like ``we
    run the DFA on the string xz'' and ``the DFA ends in an accepting state.''
    However, your written answer should be expressed purely using the 5-tuple
    definition of a DFA, the formal definition of $\delta^*$, the formal
    definition of $\mathscr{L}(D)$, etc. The underlying rationale is that this
    problem is all about formalizing our intuitions about how DFAs operate by
    using these rigorous definitions, and so the written proof should be done
    purely using those definitions.}

    \begin{shaded}
      Provide a proof here.
    \end{shaded}
\end{enumerate}

\pagebreak

In lecture, we used this theorem about distinguishable strings to prove certain
languages aren't regular:
\vspace{-2em}
\begin{quote}
  \begin{thm}
    Let $x$ and $y$ be strings where $x \not\equiv_L y$. Then $x$ and $y$
    cannot end up in the same state after being run through any DFA for the
    language $L$.
  \end{thm}
\end{quote}
We can recast this theorem in terms of the $\delta^*$ function that we just
defined above:
\vspace{-2em}
\begin{quote}
  \begin{fthm}
    Let $x$ and $y$ be strings where $x \not\equiv_L y$. Then for any DFA $D$
    for $L$, if $\delta^*$ is the extended transition function for $D$, we have
    $\delta^*(x) \neq \delta^*(y)$.
  \end{fthm}
\end{quote}
Now that you're equipped with the formal definition of $\delta^*$, you can
rigorously prove the above statement.

\begin{enumerate}[resume*]
  \item Prove the formalized theorem (the second one). Since the goal is to
    write a rigorous proof of the theorem, you should not cite the informal one
    from lecture as part of your proof.

    \annotate{Use your intuition about DFAs to think through his one, but as
    with part \ref{p:samestate} of this problem, use the 5-tuple definition of
    a DFA and the formal definition of the extended transition function in your
    proof. For example, you should not use phrases like ``run the DFA on $x$''
    or ``the DFA ends up in an accepting state,'' since you have more formal
    notation at your disposal.}

    \annotate{Once you've finished, take a minute to marvel at the fact that
    you're able to read (and prove!) statements like these. Not bad for seven
    weeks!}

    \begin{shaded}
      Provide a proof here.
    \end{shaded}
\end{enumerate}

\pagebreak

\section{Regular Languages and Equivalence Relations}

Throughout this problem set you've been working with the idea that we can take
a language $L$ over some alphabet $\Sigma$, then work with its
distinguishability relation $\not\equiv_L$. A closely related binary relation
is the \emph{indistinguishability} relation for $L$, denoted
$\boldsymbol{\equiv_L}$. It's also a binary relation over $\Sigma^*$, and its
definition is the negation of the one for distinguishability:
$$
  x \equiv_L y \text{ if } \forall w \in \Sigma^*.\ (xw \in L \leftrightarrow yw
  \in L).
$$
Amazingly, this is always an equivalence relation, regardless of what $L$ is!

\begin{enumerate}[label=\roman*.]
  \item Prove that if $L$ is a language over $\Sigma$, then $\equiv_L$ is an
    equivalence relation over $\Sigma^*$.

    \annotate{You've seen how to prove that a binary relation is an equivalence
    relation, how to prove biconditionals, and how to work with
    universally-quantified statements. This proof is going to look very similar
    to the proofs that you did on Problem Set 3, with the only notable
    exception being that it involves proofs with strings. So, for example,
    don't include first-order logic notation in your proof, make sure to
    properly scope and introduce your variables, etc.}

    \begin{shaded}
      Provide a proof here.
    \end{shaded}
\end{enumerate}

\pagebreak

Let's make this more concrete. Let $\Sigma = \{a, b\}$ and consider the
language $M = \{w \in \Sigma^* \mid$ the number of \ttt{b}'s in $w$ is
congruent to 1 modulo 5 or to 3 modulo 5\}. For example, $\ttt{a\match{b}a} \in
M, \ttt{\match{b}aaa\match{b}aaa\match{b}} \in M$, and $\ttt{\match{bbbbbb}}
\in M$, but $\ttt{aa} \notin M$ and $\ttt{a\match{bb}a}\notin M$.

\begin{enumerate}[resume*]
  \item List all the equivalence classes of $\equiv_M$, and give a system of
    representatives for $\equiv_M$. Express your answer using formal
    mathematical notation. No justification is required.

    \annotate{Remember that an equivalence relation should partition all the
    elements of its underlying set, so you should find that every string $w \in
    \Sigma^*$ belongs to exactly one of the equivalence classes.}

    \begin{shaded}
      Write your answer here.
    \end{shaded}
\end{enumerate}

\pagebreak

You might have noticed that each equivalence class of $\equiv_M$ either
consists of a bunch of strings not in $M$ or of a bunch of strings that are in
$M$. That's not a coincidence!

\begin{enumerate}[resume*]
  \item Let L be a language over some alphabet $\Sigma$ and let $x \in
    \Sigma^*$ be some string. Prove that either \textit{every string} in
    $[x]_{\equiv_L}$ is in $L$ or that \textit{no strings} in $[x]_{\equiv_L}$
    are.

    \begin{shaded}
      Provide a proof here.
    \end{shaded}
\end{enumerate}

\pagebreak

The \emph{index} of an equivalence relation $R$, denoted \emph{I(R)}, is the
number of equivalence classes of $R$. This quantity might be finite, or it
might be an infinite cardinality like $\aleph_0$, or even one of the infinities
bigger than that. Armed with the idea of an index, we can state a powerful
theorem about finite automata:
\vspace{-2em}
\begin{quote}
  \begin{thm}
    If $L$ is a language over $\Sigma$, then every DFA for $L$ must have at
    least $I(\equiv_L)$ states.
  \end{thm}
\end{quote}
In other words, there's a connection between the number of equivalence classes
of a particular binary relation and the minimum sizes of DFAs for that
language!

\begin{enumerate}[resume*]
  \item Prove the above theorem. Feel free to use the \emph{axiom of choice},
    which says that every equivalence relation has at least one system of
    representatives.

    \annotate{Proving this theorem is mostly an exercise in connecting together
    ideas you've seen used in other places. Think about the relationship
    between indices and systems of representatives, between distinguishability
    and indistinguishability, and between what you're doing here and what
    you've done earlier on this problem set.}

    \begin{shaded}
      Provide a proof here.
    \end{shaded}
\end{enumerate}

There's a lovely intuition for this theorem. You can think of the
indistinguishability relation for a language $L$ as pinning down the idea ``a
DFA for $L$ can't tell the difference between these two strings.'' If you think
back to our intuition behind DFA design -- build a DFA where each state keeps
track of some different piece of information -- then you can think of
$I(\equiv_L)$ as capturing the number of different pieces of information you'd
need to remember. The theorem then says that if you want to build a DFA for a
language $L$, you'll need at least one state per piece of information.

\pagebreak

We've got two wonderful Optional Fun Problems here for you to work through.
Each of these problems are questions we considered putting onto the main
problem set but decided not to include to keep the length down. So feel free to
work through one or both of these, and submit answers to at most one of them.
You know the drill -- if you submit answers to more than one problem, we'll
choose which one to grade based on a whim. \smiley

\section*{Optional Fun Problem One: Generalized Fooling Sets}

In Problem Seven, you used distinguishability to lower-bound the size of DFAs
for a particular language. Unfortunately, distinguishability is not a powerful
enough technique to lower-bound the sizes of NFAs. In fact, it's in general
quite hard to bound NFA sizes; there's a \$1,000,000 prize for anyone who finds
an efficient algorithm (for some precise definition of ``efficient'') that,
given an arbitrary NFA, converts it to the smallest possible equivalent NFA!

Although it's generally difficult to lower-bound the sizes of NFAs, there are
some techniques we can use to find lower bounds on the sizes of NFAs. Let $L$
be a language over $\Sigma$. A \emph{generalized fooling set} for $L$ is a set
$\mathscr{F} \subseteq \Sigma^* \times \Sigma^*$ is a set with the following
properties:

\begin{itemize}
  \item For any $(x, y) \in \mathscr{F}$, we have $xy \in L$.
  \item For any distinct pairs $(x_1, y_1), (x_2, y_2) \in \mathscr{F}$, we
    have $x_1y_2 \not\in L$ or $x_2y_1 \not\in L$ (this is an inclusive OR.)
\end{itemize}
Prove that if $L$ is a language and there is a generalized fooling set
$\mathscr{F}$ for $L$ that contains $n$ pairs of strings, then any NFA for $L$
must have at least $n$ states.

\begin{shaded}
  Provide a proof here.
\end{shaded}

\pagebreak

\section*{Optional Fun Problem Two: Why Finite?}
A \emph{deterministic infinite automaton}, or \emph{DIA}, is a generalization
of a DFA in which the automaton has infinitely many different states.  Formally
speaking, a DIA is given by the same 5-tuple definition as a DFA, except that
$Q$ must be an infinite set. Since DIAs have infinitely many states, they're
mostly an object of purely theoretical study. You couldn't actually build one
in the real world.

Prove that if $L$ is an arbitrary language over some alphabet $\Sigma$, then
there is a DIA that accepts $L$ (that is, the DIA accepts every string in $L$
and rejects every string not in $L$.) To do so, show how to start with a
language $L$, formally define a 5-tuple corresponding to a DIA for $L$, then
formally prove that that DIA accepts all and only the strings in $L$ by using
the formal definition of what the language of an automaton is.

\begin{shaded}
  Provide a proof here.
\end{shaded}

\end{document}
