\documentclass[12pt]{article}

\usepackage{fullpage,amsmath,amsfonts}

\usepackage{tikz}
\usetikzlibrary{automata, positioning, arrows}

\tikzset{->, % makes the edges directed
         >=stealth', % makes the arrow heads bold
         node distance=3cm, % specifies the minimum distance between
                            % two nodes. Change if necessary.
         every state/.style={thick, fill=gray!10}, % sets the
                            % properties for each `state` node
         initial text=$ $,  % sets the text that appears on the start arrow
}


\begin{document}

\title{Basics of Information Systems}
\author{Winter Semester 2022--23}
\date{For discussion on Wednesday, November 30, 2022}
\maketitle

\begin{enumerate}
\item Construct a binary ``add by one'' transducer.  The input number
shall be fed into the transducer starting with the least significant
binary digit.  The output shall be the input plus one, also starting
from the least significant digit.

\item Consider the following non-deterministic FSA:
\begin{center}
\begin{tikzpicture}[baseline=(q1.base)]
  \node[state, initial] (q1) {$A$};
  \node[state, accepting, below right of=q1] (q3) {$C$};
  \node[state, above right of=q3] (q2) {$B$};
  \draw (q1) edge[loop above] node{$0, 1$} (q1)
        (q1) edge[below] node{$1$} (q2)
        (q2) edge[loop right] node{$1$} (q2)
        (q3) edge[bend left, below right] node{$0$} (q2)
        (q3) edge[below left] node{$0, 1$} (q1)
        (q2) edge[bend right, above] node{$1$} (q1)
        (q2) edge[bend left, below right] node{$1$} (q3);  
\end{tikzpicture}
\end{center}
\begin{enumerate}
\item Write out a corresponding regular expression.
\item Convert the non-deterministic into an equivalent deterministic
FSA.
\end{enumerate}

\item Write regular expressions to match the following sets of binary
strings.  Use the classical regular expression syntax.  Then draw the
corresponding FSA.

\begin{enumerate}
\item $0$ or $11$ or $101$,
\item ends with $00$,
\item contains at least three $1$s,
\item starts and ends with the same character.

\end{enumerate}


\end{enumerate}
\end{document}
