\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 23, 2022}
\maketitle

\begin{enumerate}
\item Describe an algorithm which takes an string containing upper and
lower case characters encoded in ASCII and outputs the same string in
all lower case.

For simplicity, assume that your input string does not contain any
symbols other than characters of the Latin alphabet.  You may describe
your algorithm in pseudo-code or in Python.

\item How many characters can we encode with a mixed 8/16 bit
representation if we insist that an 8 bit character always has 0 in
the first bit, and a 16 bit character always as a 1 in the first bit
of each of its bytes?

\item List at least three advantages of the UTF-8 encoding over the
UTF-16 encoding of Unicode characters.

\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.
\end{enumerate}
\end{document}
