\documentclass[12pt]{article}

\usepackage[T1]{fontenc} 
\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{Foundations of Information Systems}
\author{Winter Semester 2023--24, Exercise 6}
\date{For discussion on Wednesday, November 29, 2023}
\maketitle


\begin{enumerate}

\item Which strings do the following finite state machines accept?
\begin{enumerate}
\item

\begin{tikzpicture}[baseline=(q1.base)]
  \node[state, initial] (q1) {$S_0$};
  \node[state, right of=q1] (q2) {$S_1$};
  \node[state, accepting, right of=q2] (q3) {$S_2$};
  \draw (q1) edge[loop above] node{$a$} (q1)
        (q1) edge[above] node{$b$} (q2)
        (q2) edge[loop above] node{$b$} (q2)
        (q2) edge[above] node{$a$} (q3);
\end{tikzpicture}
\item

\begin{tikzpicture}[baseline=(q1.base)]
  \node[state, initial] (q1) {$S_0$};
  \node[state, right of=q1] (q2) {$S_1$};
  \node[state, right of=q2] (q3) {$S_2$};
  \node[state, accepting, right of=q3] (q4) {$S_3$};
  \draw (q1) edge[loop below] node{$0$} (q1)
        (q1) edge[above] node{$1$} (q2)
        (q2) edge[loop below] node{$1$} (q2)
        (q2) edge[above] node{$0$} (q3)
        (q3) edge[bend left, above] node{$1$} (q4)
        (q4) edge[bend left, below] node{$0$} (q3)
        (q4) edge[bend left=45, below] node{$1$} (q2)
        (q3) edge[bend right=45, above] node{$0$} (q1);  
\end{tikzpicture}
\end{enumerate}
\item Draw a finite state machine that accepts any string from the
alphabet ${a,b}$ with an even number of $a$s.

\item Draw a finite state machine that checks if a given 7-bit input
corresponds to a number digit (“0”, \ldots , “9”) encoded in ASCII.
\end{enumerate}

\end{document}
