\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 6}
\date{For discussion on Wednesday, November 26, 2025}
\maketitle

\begin{enumerate}

\item Consider the following non-deterministic 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$};
  \node[state, right of=q2] (q3) {$C$};
  \node[state, accepting, right of=q3] (q4) {$D$};
  \draw (q1) edge[loop above] node{$\text{[a-z]}:\varepsilon$} (q1)
        (q1) edge[above] node{$\text{c}:\text{d}$} (q2)
        (q2) edge[above] node{$\text{a}:\text{o}$} (q3)
        (q3) edge[above] node{$\text{t}:\text{g}$} (q4)
        (q4) edge[loop above] node{$\text{[a-z]}:\varepsilon$} (q4);
\end{tikzpicture}
\end{center}

\begin{enumerate}
\item What does this transducer do?
\item Convert this non-deterministic transducer into a deterministic
transducer.
\end{enumerate}
\emph{Note:} The output symbol $\varepsilon$ denotes that no output is
issued.  In part (b), you may also encounter transitions that read a
single character, but issue several characters.


\item Is it possible to construct a finite state transducer that sorts
a string of characters from the Latin alphabet in increasing order?

\item Recall the ``simple language'' from class, which has
non-negative integer variables, the statements \texttt{incr(X)} and
\texttt{decr(X)}, as well as while loops of the form
\begin{verbatim}
while(X):
    loop body
\end{verbatim}
In class, we looked at a macro $\mathtt{Y} \leftarrow \mathtt{X}$
which assigns the value of \texttt{X} to \texttt{Y}, while setting
\texttt{X} to zero.  Modify this example so that the end of the
operation, \texttt{X} retains its original value.

\end{enumerate}
\end{document}

