\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{Foundations of Information Systems}
\author{Winter Semester 2025--26, Exercise 5}
\date{For discussion on Wednesday, November 19, 2025}
\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.

\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}
\newpage
\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 Convert the non-deterministic into an equivalent deterministic
FSA.
\item Write out a corresponding regular expression.
\end{enumerate}

\item Consider the following finite state transducer:

\begin{center}
\begin{tikzpicture}[baseline=(q1.base),
                    ->, % 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
                   ]
  \node[state, initial] (q1) {$A$};
  \node[state, right of=q1] (q2) {$B$};
  \draw (q1) edge[loop above] node{$0:0$} (q1)
        (q2) edge[loop right] node{$1:1$} (q2)
        (q1) edge[bend right, below] node{$1:0$} (q2) 
        (q2) edge[bend right, above] node{$0:1$} (q1);
\end{tikzpicture}
\end{center}

\begin{enumerate}
\item Describe the function that is performed by this transducer.

\item The transducer can be used as a ``multiply-by-two'' machine.
How do you need to organize input and output of the transducer so that
it performs this function correctly?

\end{enumerate}

\item Construct a binary ``add-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.


\end{enumerate}


\end{document}
