Recitation 1 latex source
This file is provided to help students create crib sheets
in latex if they wish. Some formatting was removed for clarity.
It is missing some macros, but you can figure out what they are
by looking at the pdf image. It is not a working latex file.
\chapter{Recitation 01: Finite Automata, Regular Languages}
In this recitation, we will review finite automata and see several examples of how to construct them to recognize specific languages. We will also review regular languages and regular operations, concluding with two methods of proving that all finite languages are regular.
\section{Logistics}
Recitations will primarily be for reviewing lecture material and providing supplementary examples and exercises. They are optional, but if you find them useful, then you're encouraged to attend. Additionally, TAs will make note of attendance and participation, which may be used to improve low grades.
Recitation notes will be published shortly after each recitation; they may differ slightly from the content of your recitation due to variations in different instructor sections.
\section{Finite Automata}
A \textit{finite automaton} is a model of computation consisting of finitely many states and transitions.
\marginnote{We'll see several models of computation throughout the course; finite automata are among the simplest because the number of states is \textit{finite}.} In particular, the states include exactly one \textit{start state} and zero or more \textit{accept states}. The strings inputted into a finite automaton consist of members of a specified alphabet, often $\{0,1\}$. The formal definition of a \textit{deterministic finite automaton} (or \textit{DFA}), expressed as a 5-tuple $(Q, \Sigma, \delta, q_0, F)$, was described in Lecture 1.
\marginnote{To review the formal definition of a finite automaton, see Definition 1.5 in the textbook.}
The \textit{language} of a finite automaton is the set of all strings that it accepts. Formally, a DFA $M = (Q, \Sigma, \delta, q_0, F)$ \textit{accepts} a string $w = w_1w_2 \cdots w_n$, where $w_i \in \Sigma$, if $\exists\; r_0, r_1, ..., r_n \in Q$ such that
\begin{enumerate}
\item $r_0 = q_0$
\item $r_i = \delta(r_{i-1}, w_i)$ for all $i = 1, ..., n$
\item $r_n \in F$.
\end{enumerate}
\begin{exercise}
Construct a DFA that recognizes each of the following languages, where $\Sigma = \{0,1\}$:
\begin{enumerate}
\item $\Sigma^*$
\marginnote{Remember that $\Sigma^*$ is the set of all strings consisting of zero or more $0$s and $1$s.}
\item $\emptyset$
\item $\{ \varepsilon \}$
\end{enumerate}
\end{exercise}
\begin{solution} We construct DFAs for each of the three languages.
\begin{enumerate}
\item $\Sigma^*$
\marginnote{The only state is both the start state and the only accept state. This means that any string that enters the DFA will be accepted!}
\begin{tikzpicture}[shorten >=1pt, node distance=2cm, on grid, auto]
% Define states
\node[state, initial, accepting] (q0) {$q_0$};
% Loop transitions
\path[->]
(q0) edge[loop above] node {0, 1} (q0);
\end{tikzpicture}
\item $\emptyset$
\marginnote{A small modification from the above: now no strings should be accepted, so we simply remove the accept state.}
\begin{tikzpicture}[shorten >=1pt, node distance=2cm, on grid, auto]
% Define states
\node[state, initial] (q0) {$q_0$};
% Loop transitions for both 0 and 1
\path[->]
(q0) edge[loop above] node {0, 1} (q0);
\end{tikzpicture}
\item $\{ \varepsilon \}$
\marginnote{All strings consisting of at least one $0$ or $1$ will lead us to $q_1$ and never return to $q_0$, so they will be rejected.}
\begin{tikzpicture}[shorten >=1pt, node distance=2.5cm, on grid, auto]
% Define states
\node[state, initial, accepting] (q0) {$q_0$};
\node[state] (q1) [right=of q0] {$q_1$};
% Transitions
\path[->]
(q0) edge [above] node {0, 1} (q1)
(q1) edge [loop above] node {0, 1} (q1);
\end{tikzpicture}
\end{enumerate}
\end{solution}
\begin{exercise}
Construct a DFA that recognizes each of the following languages with the given $\Sigma$:
\begin{enumerate}
\item $\Sigma = \{0, 1, ..., 9\}$, $A_{18404} = \{18404\}$.
\item $\Sigma = \{a, b\}$, $A_\text{even} = \{ w \,|\, w$ has an even number of $a$'s\}.
\end{enumerate}
\end{exercise}
\begin{solution}
We construct DFAs for each of the two languages.
\begin{enumerate}
\item $\{ 18404\}$
\begin{tikzpicture}[shorten >=1pt, node distance=2.5cm, on grid, auto]
% Define states
\node[state, initial] (q0) {$q_0$};
\node[state] (q1) [right=of q0] {$q_1$};
\node[state] (q2) [right=of q1] {$q_2$};
\node[state] (q3) [right=of q2] {$q_3$};
\node[state] (q4) [right=of q3] {$q_4$};
\node[state, accepting] (q5) [right=of q4] {$q_5$};
% Transitions
\path[->]
(q0) edge [above] node {$1$} (q1)
(q1) edge [above] node {$8$} (q2)
(q2) edge [above] node {$4$} (q3)
(q3) edge [above] node {$0$} (q4)
(q4) edge [above] node {$4$} (q5);
% Dead state and transitions to dead state for any other input
\node[state] (qd) [below left=of q3] {$q_d$};
\path[->]
(q0) edge [right] (qd)
(q1) edge [right] (qd)
(q2) edge [right] (qd)
(q3) edge [right] (qd)
(q4) edge [left] (qd)
(q5) edge [left] (qd)
(qd) edge [loop below] (qd);
\end{tikzpicture}
\marginnote{An arrow with no label implies that all alphabet members not included in any other transition from that state will follow this arrow. For example, from $\delta( q_2, n) = q_d$ for all $n \neq 4$.}
Here, $q_d$ represents the ``\textit{dead state}.'' Once we land in this state, we will never leave, so the input will not be accepted.
\marginnote{Note that $q_1$ in Exercise $1.3$ is also a dead state!}
\item $\{w \,|\, w$ has an even number of $a$'s\}
\marginnote{Being in $q_\text{even}$ represents that we have read in an even number of $a$'s; being in $q_\text{odd}$ represents that we have read in an odd number of $a$'s.}
\begin{tikzpicture}[shorten >=1pt, node distance=3cm, on grid, auto]
% Define states
\node[state, initial, accepting] (q0) {$q_\text{even}$}; % Even number of a's
\node[state] (q1) [right=of q0] {$q_\text{odd}$}; % Odd number of a's
% Transitions
\path[->]
(q0) edge [loop above] node {b} (q0)
(q0) edge [bend left] node {a} (q1)
(q1) edge [loop above] node {b} (q1)
(q1) edge [bend left] node {a} (q0);
\end{tikzpicture}
\end{enumerate}
\end{solution}
When constructing DFAs, it's useful to think of each state as a \textit{possibility} for the value that the machine cares about. In Exercise $2.2$ above for example, the value that the machine cares about is whether there is an even or odd number of $a$'s so far: in other words, the \textit{parity} of the number of $a$'s. Since there are two possible parities, we have two states.
\begin{exercise}
With $\Sigma = \{1\}$ (unary strings), construct a DFA that recognizes $A_3 = \{w \,|\, w$ has length a multiple of 3\}. Then, by generalizing this idea, provide a formal definition of a DFA recognizing $A_n = \{w \,|\, w$ has length a multiple of $n$\}.
\end{exercise}
\textit{Hint.} What is the value that the machine needs to keep track of? How many possibilities are there for that value?
\begin{solution}
We know that the DFA should keep track of a value related to the length of the input; however, we don't care about the actual length as much as whether it is divisible by 3. Thus, we create three states to represent the \textit{length modulo 3} of the input so far.
\marginnote{``Length modulo 3'' is the remainder when we divide the length by 3.}
\marginnote{We start at $q_0$, representing that the current length is $0$ mod $3$. Note that this is also the accept state, since we want to accept strings with length $0$ mod $3$. On the next 1, the length becomes $1$ mod $3$, then $2$ mod $3$, then back to $0$ mod $3$, etc.}
\vspace{0.5em}
\begin{tikzpicture}[shorten >=1pt, node distance=3cm, on grid, auto]
% Define states in a triangular layout
\node[state, initial, accepting] (q0) at (0, 0) {$q_0$}; % Remainder 0
\node[state] (q1) at (2, 2.5) {$q_1$}; % Remainder 1
\node[state] (q2) at (4, 0) {$q_2$}; % Remainder 2
% Transitions
\path[->]
(q0) edge [left] node {1} (q1)
(q1) edge [left] node {1} (q2)
(q2) edge [above] node {1} (q0);
\end{tikzpicture}
For arbitrary $n$, we want a cycle like the above, but consisting of $n$ states, representing the length being $0, 1, ..., n-1$ modulo $n$. $M = (Q, \Sigma, \delta, q_0, F)$ recognizes $A_n$, where
\begin{align*}
Q &= \{ q_0, ..., q_{n-1} \} \\
\Sigma &= \{ 1 \} \\
\delta(q_i, 1) &= \begin{cases}
q_0 & i = n-1 \\
q_{i+1} & \text{else} \\
\end{cases} \\
q_0 &= q_0 \\
F &= \{q_0\}
\end{align*}
\end{solution}
\section{Regular Languages}
A \textit{regular language} is any set of strings that is recognized by some finite automaton.
Let $L_1 = \{a, b\}$, $L_2 = \{b, c\}$. In Lecture 1, we defined the following \textit{regular operations}:
\begin{itemize}
\item Union ($\cup$)
Example: $L_1 \cup L_2 = \{a, b, c\}$.
\item Concatenation ($\circ$)
Example: $L_1 \circ L_2 = L_1L_2 = \{ab, ac, bb, bc\}$.
\item Star ($*$)
Examples: $\emptyset^* = \{ \varepsilon \}$, $L_1^* = \{ \varepsilon, a, b, aa, ab, ba, bb, aaa, aab, ... \}$.
\end{itemize}
\begin{theorem}
Every finite language is regular.
\end{theorem}
\begin{proof}[Proof 1 (construction)]
Let $L = \{w_1, w_2, ..., w_n\}$ be a finite language. Define $k$ to be the maximum length of a string in $L$, or $k = \max_{1 \leq i \leq n} |w_i|$. Construct a tree of depth $k+1$, where each state splits into two new states (one for $0$ and one for $1$). See the example below for concreteness. Note that there is now a unique path for every string of length $k$.
\marginnote{Note that it would not be possible to find $k$ for an infinite language, so this construction only applies to finite languages.}
For each $w_i \in L$, add an accept state corresponding to the state reached after processing $w_i$. This ensures that strings lead to an accept state if and only if the string is a member of $L$. Thus, this construction recognizes $L$, which shows that $L$ is regular.
\end{proof}
For example, the following is the DFA for $L = \{0, 10, 000, 001\}$ using this construction.
\newpage
\marginnote{In additiona, there is an dead state from which states
$q_7, ..., q_{14}$ lead to on any input, since we don't want to accept any
strings of length longer than 3. We haven't drawn the dead state or its
associated transitions to simplify the diagram.}
\begin{tikzpicture}[shorten >=1pt, node distance=1.5cm and 2.5cm, on grid, auto]
% Level 0 (Root)
\node[state, initial] (q0) {$q_0$}; % Root node
% Level 1
\node[state, accepting] (q1) [below right=of q0, yshift=-0.5] {$q_1$};
\node[state] (q2) [above right=of q0, yshift=0.5] {$q_2$};
% Level 2
\node[state] (q3) [below right=of q1] {$q_3$};
\node[state] (q4) [above right=of q1, yshift=-0.75cm] {$q_4$};
\node[state, accepting] (q5) [below right=of q2, yshift=0.75cm] {$q_5$};
\node[state] (q6) [above right=of q2] {$q_6$};
% Level 3
\node[state, accepting] (q7) [below right=of q3] {$q_7$};
\node[state, accepting] (q8) [above right=of q3, yshift=-1.5cm] {$q_8$};
\node[state] (q9) [below right=of q4, yshift=0.5cm] {$q_9$};
\node[state] (q10) [above right=of q4, yshift=-1.5cm] {$q_{10}$};
\node[state] (q11) [below right=of q5, yshift=1.5cm] {$q_{11}$};
\node[state] (q12) [above right=of q5, yshift=-0.5cm] {$q_{12}$};
\node[state] (q13) [below right=of q6, yshift=1.5cm] {$q_{13}$};
\node[state] (q14) [above right=of q6] {$q_{14}$};
% Transitions for Level 0 to Level 1
\path[->]
(q0) edge node {0} (q1)
(q0) edge node {1} (q2);
% Transitions for Level 1 to Level 2
\path[->]
(q1) edge node {0} (q3)
(q1) edge node {1} (q4)
(q2) edge node {0} (q5)
(q2) edge node {1} (q6);
% Transitions for Level 2 to Level 3
\path[->]
(q3) edge node {0} (q7)
(q3) edge node {1} (q8)
(q4) edge node {0} (q9)
(q4) edge node {1} (q10)
(q5) edge node {0} (q11)
(q5) edge node {1} (q12)
(q6) edge node {0} (q13)
(q6) edge node {1} (q14);
\end{tikzpicture}
\begin{proof}[Proof 2 (closure under union)]
Again let $L = \{w_1, w_2, ..., w_n\}$ be a finite language. Let $L_i := \{w_i\}$ for $i = 1, ..., n$. For each $i$, we can construct a DFA that recognizes $L_i$ in the same manner as Exercise $2.1$ ($A_{18404}$). Thus, $L_i$ is a regular language. In Lecture 1, we showed that regular languages are closed under union. We know that $L = L_1 \cup L_2 \cup \cdots \cup L_n$, so $L$ is also regular.
\end{proof}