\documentclass[12pt]{article}
\usepackage{fullpage}
\usepackage{amsmath,amssymb,amsthm}
\begin{document}
\begin{center}
\large\bf University of Waterloo\\
CS~360 --- Introduction to the Theory of Computing\\
Fall 2017\\
Problem Set 1\\
\end{center}
\bigskip\bigskip
\noindent{\it Handed out Thursday, September 7, 2017}
\bigskip
\noindent{\it Due Thursday, September 14, 2017, at 5 PM. Submit to
LEARN.}
\bigskip\bigskip
Finite automata can be described in at least two ways: by drawing
the transition diagram, or by explicitly describing all five pieces
$Q, \Sigma, \delta, q_0, F$ that define the automaton. In this problem
set, you will do both.
\medskip
First, transition diagrams:
\bigskip
\noindent 1. [20 marks]
For each of the following, draw the transition diagram
of a deterministic finite automaton (DFA) that recognizes the specified
language. Make sure that the initial state is clearly labeled,
and that all accepting states are drawn with two concentric
circles. Be sure to draw a {\it complete\/} automaton, so that
every state has an arrow out for each letter in the alphabet.
Briefly explain your construction in English.
Try to find the smallest DFA (that is, the smallest number of states)
you can. Although it is not necessary to find the smallest possible
automaton, marks will be deducted if your automaton is excessively
complicated. The most crucial part of your construction, however,
is your English explanation. No formal proof is necessary.
\medskip
\noindent (a) [5 marks]
The set of strings over $\lbrace {\tt a, b} \rbrace$
containing at most one pair of two consecutive $\tt a$'s and at most one pair
of two consecutive $\tt b$'s.
Note: the string $\tt aaa$ is considered to contain {\it two\/}
pairs of two consecutive $\tt a$'s, which overlap each other.
\medskip
\noindent (b) [5 marks] The set of nonempty
strings $x$ over $\lbrace {\tt a, b} \rbrace$
such that every other symbol (starting with the {\it last\/} symbol and
working backwards) is an $\tt a$. For example,
$\tt a$, $\tt aa$, $\tt ba$, and $\tt baaaba$ are included
in the specification, but $\epsilon$ and $\tt abbaa$ are not.
\medskip
\noindent (c) [5 marks]
The set of strings over $\lbrace {\tt a, b, c} \rbrace$ such that at
least one of the three symbols appears at least twice (not necessarily
consecutively).
\medskip
\noindent (d) [5 marks]
The set of strings over $\lbrace {\tt a, b} \rbrace$ that contain
${\tt abaab}$ as a subword.
\bigskip
Next, we'll turn to the formal definition. ``Describe'' means
``define all five pieces $Q, \Sigma, \delta, q_0, F$''.
\bigskip
\noindent 2. [10 marks]
\medskip
\noindent (a) [5 marks] For integers $n \geq 1$,
describe a DFA recognizing the language
$$L_n = \{ x \in \{ 0,1\}^* \ : x \text{ has a $1$ in the position
$n$ places from the end} \}.$$
(Here the very last symbol is $1$ place from the end.)
\medskip
\noindent (b) [5 marks]
For integers $n \geq 1$, describe a DFA recognizing the
finite language
$$\{ a^i b^i \ : 0 \leq i \leq n \}.$$
\end{document}