%
% LaTeX Problem Set Template originally designed
% by former CS103 TA Sachin Padmanabhan.
%
% Updated for Fall 2018 by Michael Zhu
% Updated for Fall 2019 by Joshua Spayd
% Updated for Fall 2020 by Lucy Lu
% Updated for Winter/Spring 2021 by Cynthia Bailey Lee
% Updated for Fall 2021 by Grant McClearn

\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}
\usepackage{enumitem}
\usepackage[T1]{fontenc}
\usepackage{inconsolata}
\usepackage{framed}
\usepackage{wasysym}
\usepackage[thinlines]{easytable}
\usepackage{hyperref}
\usepackage{wrapfig}
\hypersetup{
    colorlinks=true,
    linkcolor=blue,
    filecolor=magenta,
    urlcolor=blue,
}

\title{CS 103: Mathematical Foundations of Computing\\Problem Set \#6}
\author{[TODO: Replace this with your name(s)]}
\date{\today}

% Running author based on https://tex.stackexchange.com/questions/68308/how-to-add-running-title-and-author#answer-68310
\makeatletter
\let\runauthor\@author
\makeatother

\lhead{\runauthor}
\chead{Problem Set 6}
\rhead{\today}
\lfoot{}
\cfoot{CS 103: Mathematical Foundations of Computing --- Fall 2021}
\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}

\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{\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}}

% start MZ
\let\oldemptyset\emptyset
\renewcommand{\emptyset}{\text{\O}}
\renewcommand{\labelitemii}{$\bullet$}
\renewcommand\qedsymbol{$\blacksquare$}
\newenvironment{prf}{{\bfseries Proof.}}{\qedsymbol}
\renewcommand{\emph}[1]{\textit{\textbf{#1}}}
\newcommand{\annotate}[1]{\textit{\textcolor{blue}{#1}}}
\usepackage{mdframed}
\usepackage{float}

\makeatother
% end MZ

\definecolor{shadecolor}{gray}{0.95}

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

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

\theoremstyle{definition}
\newtheorem*{answer}{Answer}

\newtheorem{theorem}{Theorem}[section]
\newtheorem*{thm}{Theorem}
\newtheorem{corollary}{Corollary}[theorem]
\newtheorem{lemma}[theorem]{Lemma}

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

\setlength{\parindent}{0pt}

\pagestyle{fancy}

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

% Lucy
\usepackage{boxedminipage}
\newenvironment{blank}[1]{\colorbox{shadecolor}{\strut \underline{\hspace{#1}}}}
% Lucy

\begin{document}

\maketitle

\begin{center}
  \emph{Due Friday, November 5 at 2:30 pm Pacific}
\end{center}

Do not put your answers to Problems 1, 2, and 7 in this file. You'll submit those separately on Gradescope.

Here's a quick reference of symbols you may want to use in this problem set.

\begin{itemize}
    \item Alphabets are written as $\Sigma$.
    \item The set of all strings over $\Sigma$ is denoted $\Sigma^\star$
    \item The empty string is written as $\varepsilon$. The "var" here refers to a "variant" of the letter epsilon; that's the one we use in this class.
    \item Subscripts are done as is $q_{137}$; superscripts are done as $a^{137}$.
    \item You can make text render \texttt{like a typewriter} in text mode or in $\mathtt{math}$ mode.
    \item The Greek letter $\rho$ appears in Q6.
    \item The Greek letter $\delta$ appears in Q7.
\end{itemize}

\pagebreak

\section*{Problem Three: $\wp(\Sigma^*)$}
\begin{shaded}
Write your answer to Problem Three here.
\end{shaded}

\newpage

\section*{Problem Four: Much Ado About Nothing, Part II}
    i.
    \begin{shaded}
    Write your answer to Problem Four, part i. here.
    \end{shaded}
    
    ii.
    \begin{shaded}
    Write your answer to Problem Four, part ii. here.
    \end{shaded}
    
    iii.
    \begin{shaded}
    Write your answer to Problem Four, part iii. here.
    \end{shaded}
    
    iv.
    \begin{shaded}
    Write your answer to Problem Four, part iv. here.
    \end{shaded}
    
    v.
    \begin{shaded}
    Write your answer to Problem Four, part v. here.
    \end{shaded}
    
    vi.
    \begin{shaded}
    Write your answer to Problem Four, part vi. here.
    \end{shaded}

\newpage

\section*{Problem Five: Hard Resets}
Fill in the table and blank to Problem Five below.
\begin{shaded}

\begin{center}
\begin{tabular}{ |c|c|c| } 
 \hline
 state & \texttt{a} & \texttt{b} \\ \hline
  &  &  \\ \hline
  &  &  \\ \hline
  &  &  \\ \hline
  &  &  \\ \hline
  &  &  \\ \hline
  &  &  \\ \hline
  &  &  \\ \hline
  &  &  \\ \hline
\end{tabular}
\end{center}

Sample hard reset string: \blank{1cm}.

\end{shaded}

\newpage

\section*{Problem Six: Induction on Strings}
    i. Fill in the blanks to Problem Six, part i. below.
    \begin{shaded}
    1. $\rho(\texttt{r}) = \blank{1cm}$. \\
    2. $\rho(\texttt{sr}) = \blank{1cm}$. \\
    3. $\rho(\texttt{rrs}) = \blank{1cm}$. \\
    4. $\rho(\texttt{r}^{100} \texttt{s}^{100}) = \blank{1cm}$.
    \end{shaded}
    
    ii. Fill in the blanks to Problem Six, part ii. below.
    \begin{shaded}
    \begin{center}
        \begin{boxedminipage}{0.9\textwidth}
            \emph{Theorem:} For any string $w \in \Sigma^*$, we have $|\rho(w)| = |w|$. \\
            \emph{Proof:} Let $P(w)$ be the statement ``\blank{1cm}.'' We will prove by induction that $P(w)$ holds for all $w \in \Sigma^\star$, from which the theorem follows. \\
            As a base case, we prove $P(\blank{1cm})$, namely, that $\blank{1cm}$. $\blank{1cm}$. \\
            For our inductive step, pick some $x \in \Sigma^*$ and $a \in \Sigma$ and assume $P(\blank{1cm})$ is true, meaning that $\blank{1cm}$. We need to show $P(\blank{1cm})$ is true, that $\blank{1cm}$. To see this, note that    
            \[\begin{aligned}
            \abs{\rho(\blank{1cm})} &= \abs{\blank{1cm}} \\
                       &= \blank{1cm} + 1   \\
                       &= \blank{1cm} + 1 \hspace{1.1cm} \text{(by our IH)} \\
                       &= \blank{1cm} \text.   \\
            \end{aligned}\]
            This means that $\blank{1cm}$, so $P(\blank{1cm})$ holds, completing the induction. \qedsymbol \\
        \end{boxedminipage}
    \end{center}
    \end{shaded}
    
    iii.
    \begin{shaded}
    Write your answer to Problem Six, part iii. here.
    \end{shaded}
    
    iv.
    \begin{shaded}
    Write your answer to Problem Six, part iv. here.
    \end{shaded}
    
\newpage

\section*{Problem Eight: Concatenation, Kleene Stars, and Complements}
    i.
    \begin{shaded}
    Write your answer to Problem Eight, part i. here.
    \end{shaded}
    
    ii.
    \begin{shaded}
    Write your answer to Problem Eight, part ii. here.
    \end{shaded}
    
\newpage

\section*{Optional Fun Problem: Why Finite?}
\begin{shaded}
Write your answer to the Optional Fun Problem here.
\end{shaded}

\end{document}
