%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Note to students! %
% %
% This source file is provided to give example LaTeX code. We do not recommend %
% trying to compile it, since it has some advanced LaTeX dependencies. %
% Specifically, this file depends on the cse311-common.cls file (link below) %
% and LuaLaTeX. The course staff will not be able to help much with %
% configuring your system for LuaLaTeX. %
% https://courses.cs.washington.edu/courses/cse311/21sp/section/cse311-common.cls
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[section, problems]{latex-common/cse311-common}
\sectionnumber{07}
\topic{Structural Induction, Regular Expressions, Context-Free Grammars}
\begin{document}
\maketitle
\def\sP{\textsf{P}}
\def\sapp{\textsf{append}}
\def\slen{\textsf{len}}
\def\sdou{\textsf{double}}
\section{Structural Induction}
\begin{enumeratequestions}
\item Consider the following recursive definition of strings.
{\bf Basis Step: } $\texttt{\textquotedbl\textquotedbl}$ is a string
{\bf Recursive Step:} If $X$ is a string and $c$ is a character then $\textsf{append}(c,X)$ is a string.
Recall the following recursive definition of the function \textsf{len}:
$$\begin{aligned}
&\textsf{len}(\texttt{\textquotedbl\textquotedbl}) &&= 0\\
&\textsf{len}(\sapp(c,X)) &&= 1 + \textsf{len}(X)
\end{aligned}$$
Now, consider the following recursive definition:
$$\begin{aligned}
&\sdou(\texttt{\textquotedbl\textquotedbl}) &&= \texttt{\textquotedbl\textquotedbl}\\
&\sdou(\sapp(c,X)) &&= \sapp(c,\sapp(c,\sdou(X))).
\end{aligned}$$
Prove that for any string $X$, $\slen(\sdou(X)) = 2\slen(X)$.
\begin{solution}
For a string $X$, let $\textsf{P}(X)$ be ``$\slen(\sdou(X))=2\slen(X)$". We prove $\textsf{P}(X)$ for all strings $X$ by structural induction on $X$.
% Let $L$ be a list.
\begin{description}
\item [Base Case ($X$ = \texttt{\textquotedbl\textquotedbl}):]By definition, $\slen(\sdou(\texttt{\textquotedbl\textquotedbl}))=\slen(\texttt{\textquotedbl\textquotedbl})=0=2 \cdot 0 = 2\slen(\texttt{\textquotedbl\textquotedbl})$,
so $\textsf{P}(\texttt{\textquotedbl\textquotedbl})$ holds
\item [Inductive Hypothesis:] Suppose $\textsf{P}(X)$ holds for some arbitrary string $X$.
\item [Inductive Step:] \fbox{Goal: Show that $\textsf{P}(\sapp(c,X))$ holds for any character $c$.}
% Suppose that $\textsf{len}(\textsf{stutter}(L^\prime)) = 2\textsf{len}(L^\prime)$ for some list $L^\prime$.
% Note that
$$\begin{aligned}
\slen(\sdou(\sapp(c,X))) &= \slen(\sapp(c,\sapp(c,\sdou(X)))) &&\text{[By Definition of \sdou]}\\
&= 1 + \slen(\sapp(c,\sdou(X))) &&\text{[By Definition of \slen]}\\
&= 1 + 1 + \slen(\sdou(X)) &&\text{[By Definition of \slen]}\\
&= 2 + 2\slen(X) &&\text{[By IH]}\\
&= 2(1 + \slen(X)) &&\text{[Algebra]}\\
&= 2(\slen(\sapp(c,X))) &&\text{[By Definition of \slen]}\\
\end{aligned}$$
This proves $\sP(\sapp(c,X))$.
\item [Conclusion:] $\sP(X)$ holds for all strings $X$ by structural induction.
\end{description}
\end{solution}
\item Consider the following definition of a (binary)\ \textbf{Tree}:
\newcommand{\XNil}{\texttt{Nil}}
\newcommand{\XTree}[3]{\texttt{Tree}(#1, #2, #3)}
\newcommand{\Xifthenelse}[3]{\texttt{if }#1\texttt{ then }#2\texttt{ else }#3}
{\bf Basis Step: } $\bullet$ is a {\bf Tree}.
{\bf Recursive Step:} If $L$ is a {\bf Tree} and $R$ is a {\bf Tree} then $\XTree{\bullet}{L}{R}$ is a {\bf Tree}.
% And the definition of \textsf{size} on trees:
\def\slea{\textsf{leaves}}
\def\ssize{\textsf{size}}
The function $\slea$ returns the number of leaves of a {\bf Tree}. It is defined as follows:
$$\begin{aligned}
&\slea(\bullet) &&= 1\\
&\slea(\XTree{\bullet}{L}{R}) &&= \textsf{\slea}(L) + \textsf{\slea}(R)
\end{aligned}$$
Also, recall the definition of \textsf{\ssize} on trees:
$$\begin{aligned}
&\textsf{size}(\bullet) &&= 1\\
&\textsf{size}(\XTree{\bullet}{L}{R}) &&= 1 +\textsf{size}(L)+ \textsf{size}(R)
\end{aligned}$$
Prove that $\slea(T) \geq \textsf{size}(T)/2+1/2$ for all \textsf{Tree}s $T$.
\begin{solution}
For a tree $T$, let $\sP$ be $\slea(T) \geq \textsf{size}(T)/2+1/2$.
We prove $\sP$ for all trees $T$ by structural induction on $T$.
\begin{description}
\item [Base Case (T = $\bullet$):] By definition of $\slea(\bullet)$, $\slea(\bullet)=1$ and $\ssize(\bullet)=1$. So, $\slea(\bullet)=1\geq 1/2 +1/2 =\ssize(\bullet)/2+1/2$,
so $\sP(\bullet)$ holds.
\item [Inductive Hypothesis:] Suppose $\sP(L)$ and $\sP(R)$ hold for some arbitrary trees $L,R$.
\item [Inductive Step:] \fbox{Goal: Show that $\sP(\XTree{\bullet}{L}{R})$ holds.}
\begin{align*}
\slea(\XTree{\bullet}{L}{R})
&= \slea(L) + \slea(R) && \text{[By Definition of $\slea$]} \\
&\geq (\ssize(L)/2 + 1/2) + (\ssize(R)/2 + 1/2) && \text{[By IH]} \\
&= (1/2 + \ssize(L)/ 2 + \ssize(R) / 2) + 1/2 && \text{[By Algebra]} \\
&= \frac{1 + \ssize(L) + \ssize(R)}{2} + 1/2 && \text{[By Algebra]} \\
&= \ssize(T)/2 + 1/2 && \text{[By Definition of $\ssize$]}
\end{align*}
This proves $\sP(\XTree{\bullet}{L}{R})$.
\item [Conclusion:]
Thus, $\sP(T)$ holds for all trees $T$ by structural induction.
\end{description}
\end{solution}
\item
Prove the previous claim using strong induction. Define $P(n)$ as ``all
trees $T$ of size $n$ satisfy $\slea(T) \geq \ssize(T) / 2 + 1 / 2$''.
You may use the following facts:
\begin{itemize}
\item For any tree $T$ we have $\ssize(T) \geq 1$.
\item For any tree $T$, $\ssize(T) = 1$ if and only if $T = \bullet$.
\end{itemize}
If we wanted to prove these claims, we could do so by structural
induction.
Note, in the inductive step you should start by letting $T$ be an
arbitrary tree of size $k + 1$.
\begin{solution}
Let $P(n)$ be ``all trees $T$ of size $n$ satisfy $\slea(T) \geq
\ssize(T) / 2 + 1 / 2$''. We show $P(n)$ for all integers $n \geq 1$ by
strong induction on $n$.
\begin{description}
\item[Base Case:] Let $T$ be an arbitrary tree of size $1$. The only
tree with size $1$ is $\bullet$, so $T = \bullet$. By definition,
$\slea(T) = \slea(\bullet) = 1$ and thus $\ssize(T) = 1 =
1 / 2 + 1 / 2 = \ssize(T)/2 + 1/2$. This shows the base case holds.
\item[Inductive Hypothesis:] Suppose that $P(j)$ holds for all
integers $j = 1, 2, \ldots, k$ for some arbitrary integer $k \geq
1$.
\item[Inductive Step:]
Let $T$ be an arbitrary tree of size $k + 1$. Since $k + 1 > 1$,
we must have $T \neq \bullet$. It follows from the definition of a
tree that $T = \XTree{\bullet}{L}{R}$ for some trees $L$ and $R$.
By definition, we have $\ssize(T) = 1 + \ssize(L) + \ssize(R)$.
Since sizes are non-negative, this equation shows $\ssize(T) >
\ssize(L)$ and $\ssize(T) > \ssize(R)$ meaning we can apply the
inductive hypothesis. This says that $\slea(L) \geq \ssize(L) / 2
+ 1/2$ and $\slea(R) \geq \ssize(R) / 2 + 1/2$.
We have,
\begin{align*}
\slea(T) &= \slea(\XTree{\bullet}{L}{R}) \\
&= \slea(L) + \slea(R) && \text{[By Definition of $\slea$]} \\
&\geq (\ssize(L)/2 + 1/2) + (\ssize(R)/2 + 1/2) && \text{[By
IH]} \\
&= (1/2 + \ssize(L)/ 2 + \ssize(R) / 2) + 1/2 && \text{[By
Algebra]} \\
&= \frac{1 + \ssize(L) + \ssize(R)}{2} + 1/2 && \text{[By
Algebra]} \\
&= \ssize(T)/2 + 1/2 && \text{[By Definition of $\ssize$]}
\end{align*}
This shows $P(k + 1)$.
\item[Conclusion:] $P(n)$ holds for all integers $n \geq 1$ by the
principle of strong induction.
\end{description}
Note, this proves the claim for all trees because every tree $T$ has
some size $s \geq 1$. Then $P(s)$ says that all trees of size $s$
satisfy the claim, including $T$.
% \colorbox{orange}{Alternative Solution with Strong Induction}\\
% For a tree $T$, let $\sP$ be $\slea(T) \geq \textsf{size}(T)/2+1/2$.
% We prove $\sP$ for all trees $T$ by strong induction.
% \begin{description}
% \item [Base Case (T = $\bullet$):] By definition of $\slea(\bullet)$, $\slea(\bullet)=1$ and $\ssize(\bullet)=1$. So, $\slea(\bullet)=1\geq 1/2 +1/2 =\ssize(\bullet)/2+1/2$,
% so $\sP(\bullet)$ holds.
% \item [Inductive Hypothesis:] \colorbox{orange}{Suppose $\sP(X)$ holds for any subtree $X$ of $\XTree{\bullet}{L}{R}$.}
% \item [Inductive Step:] \fbox{Goal: Show that $\sP(\XTree{\bullet}{L}{R})$ holds.}
% $$\begin{aligned}
% \slea(\XTree{\bullet}{L}{R}) &= \slea(L) + \slea(R) &&\text{[By Definition of \slea]}\\
% &\geq (\ssize(L)/2+1/2) + (\ssize(R)/2+1/2) &&\text{[By IH]}\\
% &= 1 + \ssize(\XTree{\bullet}{L}{R})/2 &&\text{[By Definition of \ssize]}\\
% &\geq \ssize(\XTree{\bullet}{L}{R})/2 + 1/2 &&
% \end{aligned}$$
% \item [Conclusion:] This proves $\sP(\XTree{\bullet}{L}{R})$.
% \end{description}
% Thus, the $\sP(T)$ holds for all trees $T$.
\end{solution}
\end{enumeratequestions}
\section{Regular Expressions}
\begin{enumeratequestions}
\item Write a regular expression that matches base 10 numbers (e.g., there should be no leading zeroes).
\begin{solution}
$$0 \cup((1 \cup 2 \cup 3 \cup 4 \cup 5 \cup 6 \cup 7 \cup 8 \cup 9)(0 \cup 1 \cup 2 \cup 3 \cup 4 \cup 5 \cup 6 \cup 7 \cup 8 \cup 9)^*)$$
\end{solution}
\item Write a regular expression that matches all base-3 numbers that are divisible by 3.
\begin{solution}
$$0 \cup ((1 \cup 2)(0 \cup 1 \cup 2)^*0)$$
\end{solution}
\item Write a regular expression that matches all binary strings that contain the substring ``111'', but not the substring ``000''.
\begin{solution}
$$(01 \cup 001 \cup 1^*)^*(0 \cup 00 \cup \varepsilon)111(01 \cup 001 \cup 1^*)^*(0 \cup 00 \cup \varepsilon)$$
\end{solution}
\end{enumeratequestions}
\section{CFGs}
\begin{enumeratequestions}
\item All binary strings that end in 00.\\
\begin{solution}
$$\textbf{S} \rightarrow 0\textbf{S} \mid 1\textbf{S} \mid 00$$
\end{solution}
\item All binary strings that contain at least three 1's.\\
\begin{solution}
\begin{align*}
\textbf{S} &\rightarrow \textbf{TTT}\\
\textbf{T} &\rightarrow 0\textbf{T} \mid \textbf{T} 0\mid 1\textbf{T}\mid 1
\end{align*}
\end{solution}
\item All binary strings with an equal number of 1's and 0's.\\
\begin{solution}
$$\textbf{S} \rightarrow 0\textbf{S} 1 \textbf{S} \mid 1\textbf{S} 0 \textbf{S} \mid \varepsilon$$
and
$$\textbf{S} \rightarrow \textbf{S}\textbf{S} \mid 0\textbf{S} 1 \mid 1 \textbf{S} 0 \mid \varepsilon$$
both work. Note: The fact that all the strings generated have the property
is easy to show (by induction) but the fact that one can generate all
strings with the property is trickier. To argue this that each of these is
grammars is enough one would need to consider how the difference between
the \# of 0's seen and the \# of 1's seen occurs in prefixes of any string
with the property.
\end{solution}
\end{enumeratequestions}
\section{Walk the Dawgs}
Suppose a dog walker takes care of $n \ge$ 12 dogs.
The dog walker is not a strong person, and will walk dogs in groups of 3 or 7 at a time
(every dog gets walked exactly once). Prove the dog walker can always split the n dogs into groups of 3 or 7.
\begin{solution}
Let $P (n)$ be “a group with n dogs can be split into groups of 3 or 7 dogs.”
We will prove $P (n)$ for all natural numbers $n \ge$ 12 by strong induction.
\begin{description}
\item[Base Cases $n = 12, 13, 14,$ or $15$:] 12 = 3 + 3 + 3 + 3, 13 = 3 + 7 + 3, 14 = 7 + 7, So $P (12)$, $P(13)$, and $P(14)$ hold.
\item[Inductive Hypothesis:] Assume that $P (12)$, . . . , $P (k)$ hold for some arbitrary $k \ge$ 14.
\item[Inductive Step:] \fbox{Goal: Show $k+1$ dogs can be split into groups of size 3 or 7.}\\
We first form one group of 3 dogs. Then we can divide the remaining $k−2$ dogs into groups of 3 or 7 by the assumption $P(k−2)$.
(Note that $k \ge$ 14 and so $k − 2 \ge 12$; thus, $P (k − 2)$ is among our assumptions $P (12)$, . . . , $P (k)$.)
\item[Conclusion:] $P (n)$ holds for all integers $n \ge$ 12 by by principle of strong induction.
\end{description}
\end{solution}
\section{Reversing a Binary Tree}
Consider the following definition of a (binary) \textbf{Tree}.
\begin{description}
\item[Basis Step] \texttt{Nil} is a \textbf{Tree}.
\item[Recursive Step] If $L$ is a \textbf{Tree}, $R$ is a \textbf{Tree}, and $x$
is an integer, then $\texttt{Tree}(x, L, R)$ is a \textbf{Tree}.
\end{description}
The \textsf{sum} function returns the sum of all elements in a \textbf{Tree}.
\begin{equation*}
\begin{aligned}
&\textsf{sum}(\texttt{Nil}) &&= 0 \\
&\textsf{sum}(\texttt{Tree}(x, L, R))
&&= x + \textsf{sum}(L) + \textsf{sum}(R) \\
\end{aligned}
\end{equation*}
The following recursively defined function produces the mirror image of a
\textbf{Tree}.
\begin{equation*}
\begin{aligned}
&\textsf{reverse}(\texttt{Nil}) &&= \texttt{Nil} \\
&\textsf{reverse}(\texttt{Tree}(x, L, R))
&&= \texttt{Tree}(x, \textsf{reverse}(R), \textsf{reverse}(L)) \\
\end{aligned}
\end{equation*}
Show that, for all \textbf{Tree}s $T$ that
\begin{equation*}
\textsf{sum}(T) = \textsf{sum}(\textsf{reverse}(T))
\end{equation*}
\begin{solution}
For a \textbf{Tree} $T$, let $P(T)$ be ``$\textsf{sum}(T) =
\textsf{sum}(\textsf{reverse}(T))$''. We show $P(T)$ for all \textbf{Tree}s
$T$ by structural induction.
\begin{description}
\item[Base Case:] By definition we have $\textsf{reverse}(\texttt{Nil}) =
\texttt{Nil}$. Applying $\textsf{sum}$ to both sides we get
$\textsf{sum}(\texttt{Nil}) =
\textsf{sum}(\textsf{reverse}(\texttt{Nil}))$, which is exactly
$P(\texttt{Nil})$, so the base case holds.
\item[Inductive Hypothesis:]
Suppose $P(L)$ and $P(R)$ hold for some arbitrary \textbf{Tree}s $L$ and
$R$.
\item[Inductive Step:]
Let $x$ be an arbitrary integer. \fbox{Goal: Show $P(\texttt{Tree}(x, L,
R))$ holds.}
We have,
\begin{align*}
\textsf{sum}(\textsf{reverse}(\texttt{Tree}(x, L, R)))
&= \textsf{sum}(\texttt{Tree}(x, \textsf{reverse}(R),
\textsf{reverse}(L)))
&& \text{[Definition of \textsf{reverse}]} \\
&= x + \textsf{sum}(\textsf{reverse}(R)) +
\textsf{sum}(\textsf{reverse}(L))
&& \text{[Definition of \textsf{sum}]} \\
&= x + \textsf{sum}(R) + \textsf{sum}(L)
&& \text{[Inductive Hypothesis]} \\
&= x + \textsf{sum}(L) + \textsf{sum}(R)
&& \text{[Commutativity]} \\
&= \textsf{sum}(\texttt{Tree}(x, L, R))
&& \text{[Definition of \textsf{sum}]}
\end{align*}
This shows $P(\texttt{Tree}(x, L, R))$.
\item[Conclusion:] Therefore, $P(T)$ holds for all \textbf{Tree}s $T$ by
structural induction.
\end{description}
\end{solution}
\section{Recursively Defined Sets of Strings}
For each of the following, write a recursive definition of the sets satisfying the following properties. Briefly justify that your solution is correct.
\begin{enumeratequestions}
\item Binary strings of even length.
\begin{solution}
\textbf{Basis:} $\varepsilon \in S.$\\
\textbf{Recursive Step:} If $x \in S$, then $x00, x01, x10, x11 \in S$.\\
\textbf{Exclusion Rule:} Each element of S is obtained from the basis and a finite number of applications of the recursive step.\\
\textit{``Brief ” Justification}: We will show that $x \in S$ iff x has even length (i.e.,|x|= 2n for some $n \in \mathbb{N}$). (Note: ``brief” is in quotes here. Try to write shorter explanations in your homework assignment when possible!)
Suppose $x \in S$. If x is the empty string, then it has length 0, which is even. Otherwise, x is built up from the empty string by repeated application of the recursive step, so it is of the form $x_1x_2...x_n$, where each $x_i \in \{00,01,10,11\}$. In that case, we can see that |x|=|$x_1$|+|$x_2$|+···+|$x_n$|= 2n, which is even. Now, suppose that x has even length. If it’s length is zero, then it is the empty string, which is in S. Otherwise, it has length 2n for some $n>0$, and we can write x in the form $x_1x_2...x_n$, where each $x_i \in \{00,01,10,11\}$ has length 2. Hence, we can see that x can be built up from the empty string by applying the recursive step with $x_1$, then $x_2$, and so on up to $x_n$, which shows that $x \in S$.
\end{solution}
\item Binary strings not containing 10.
\begin{solution}
If the string does not contain 10, then the first 1 in the string can only be followed by more 1s. Hence, it must be of the form $0^m 1^n$ for some $m, n \in \mathbb{N}$.
\textbf{Basis:} $\varepsilon \in S.$
\textbf{Recursive Step: } If $x \in S$, then $0x \in S$ and $x1 \in S$.
\textbf{Exclusion Rule:} Each element of S is obtained from the basis and a finite number of applications of the recursive step.
\textit{Brief Justification:} The empty string satisfies the property, and the recursive step cannot place a 0 after a 1 since it only adds 0s on the left. Hence, every string in S satisfies the property.
In the other direction, from our discussion above, any string of this form can be written as $y = 0^m1^n$ for some $m, n \in \mathbb{N}$. We can build up the string y from the empty string by applying the rule $x \rightarrow 0x$ m times and then applying the rule $x \rightarrow x1$ n times. This shows that the string y is in S.
\end{solution}
\item Binary strings not containing 10 as a substring and having at least as many 1s as 0s.
\begin{solution}
These must be of the form $0^m1^n$ for some $m, n \in \mathbb{N}$ with $m \leq n$. We can ensure that by pairing up the 0s with 1s as they are added:
\textbf{Basis:} $\varepsilon \in S$.
\textbf{Recursive Step:} If $x \in S$, then $0x1 \in S$ and $x1 \in S$.
\textbf{Exclusion Rule:} Each element of S is obtained from the basis and a finite number of applications of the recursive step.
\textit{Brief Justification:} As in the previous part, we cannot add a 0 after a 1 because we only add 0s at the front. And since every 0 comes with a 1, we always have at least as many 1s as 0s.
In the other direction, from our discussion above, any string of this form can be written as $xy$, where $x = 0^m1^m$ and $y= 1^{n−m}$, since $n \geq m$. We can build up the string x from the empty string by applying the rule $x \rightarrow 0x1$ $m$ times and then produce the string $xy$ by applying the rule $x \rightarrow x1$ $n−m$ times, which shows that the string is in S.
\end{solution}
\item Binary strings containing at most two 0s and at most two 1s.
\begin{solution}
This is the set of all binary strings of length at most 4 \textit{except} for these:
$$000,1000,0100,0010,0001,0000,111,0111,1011,1101,1110,1111$$
Since this is a \textbf{finite set}, we can define it recursively using only basis elements and no recursive step.
\end{solution}
\end{enumeratequestions}
\end{document}