%
% Assignment 1b for CS3530 Computational Theory:
% Finite Automata
% Fall 2024
%
% Problems taken from Sipser
%

\documentclass{article}

\usepackage[margin=1in]{geometry}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage[english]{babel}
\usepackage[utf8]{inputenc}
\usepackage{ae,aecompl}
\usepackage{emp,ifpdf}
\usepackage{graphicx}

\ifpdf\DeclareGraphicsRule{*}{mps}{*}{}\fi

\empprelude{input boxes; input theory}

% skip for paragraphs, don't indent
\addtolength{\parskip}{0.5\baselineskip}
\parindent=0pt

\begin{document}
\begin{empfile}

\begin{center}
\textbf{\Large CS 3530: Assignment 1b} \\[2mm]
Fall 2024

\emph{Your Name Here}
\end{center}

\raggedright

Note: In each of the following, you should show and describe the
simpler DFAs as well as the final DFA or NFA that you construct. You must
follow the steps of each construction precisely. Do not take
shortcuts or simplify the results. You do not need to show
intermediate steps.

If a DFA is called for, an NFA is not acceptable. Be sure to include
\textit{all} states and transitions of a DFA.

\section*{Exercise 1.4c (4 points)}

\subsection*{Problem}

Each of the following languages is the intersection of two simpler
languages. In each part, construct DFAs for the simpler languages,
then combine them using the construction discussed in footnote~3
(page~46) to give the state diagram of a DFA for the language given.
In all parts $\Sigma=\{a,b\}$.

\begin{itemize}
\item[c.] Language: $\{w|w$ has an even number of $a$'s and one or
two $b$'s$\}$
\end{itemize}

\subsection*{Solution}

\section*{Exercise 1.5c (4 points)}

\subsection*{Problem}

Each of the following languages is the complement of a simpler
language. In each part, construct a DFA for the simpler language,
then use it to give the state diagram of a DFA for the language
given. In all parts $\Sigma=\{a,b\}$.

\begin{itemize}
\item[c.] Language: $\{w|w$ contains neither the substrings $ab$ nor
$ba\}$
\end{itemize}

\subsection*{Solution}

\section*{Exercise 1.8b (3 points)}

\subsection*{Problem}

Use the construction given in the proof of Theorem~1.45 to give the
state diagrams of NFAs recognizing the union of the languages given.

\begin{itemize}
\item[b.] Language: $L_1\cup L_2$ where $L_1$ is the language from
1.6c and $L_2$ is the language from 1.6f \\ (note: both languages are
from assignment 1a)

Language from 1.6c: $\{w|w$ contains the substring $0101$, i.e.,
$w=x0101y$ for some $x$ and $y\}$

Language from 1.6f: $\{w|w$ doesn't contain the substring $110\}$
\end{itemize}

\subsection*{Solution}

\section*{Exercise 1.9b (3 points)}

\subsection*{Problem}

Use the construction given in the proof of Theorem~1.47 to give the
state diagrams of NFAs recognizing the concatenation of the
languages given.

\begin{itemize}
\item[b.] Language: $L_1\circ L_2$ where $L_1$ is the language from
1.6b and $L_2$ is the language from 1.6m \\ (note: both languages are
from assignment 1a)

Language from 1.6b: $\{w|w$ contains at least three $1$s$\}$

Language from 1.6m: The empty set
\end{itemize}

\subsection*{Solution}

\section*{Exercise 1.16 (6 points)}

\subsection*{Problem}

Use the construction given in Theorem~1.39 to convert the following
two nondeterministic finite automata to equivalent deterministic
finite automata.

\begin{center}
\begin{tabular}{cc}
\begin{emp}(0,0)
  bignodes;
  u := 1.5cm;
  node.a1("1"); a1.c=(0,0);
  node.a2("2"); a2.c=(0,-u);
  makestart(a1); makefinal(a1);
  drawboxed(a1,a2);
  edge(a1,a2,curve,AB);
  edge(a2,a1,curve,B);
  loop(a1,right,A);
\end{emp}
&
\qquad\begin{emp}(0,0)
  bignodes;
  u := 1.5cm;
  s := u*sqrt(2);
  node.b1("1"); b1.c=(0,0);
  node.b2("2"); b2.c=(s,0);
  node.b3("3"); b3.c=(.5s,-u);
  makestart(b1); makefinal(b2);
  drawboxed(b1,b2,b3);
  edge(b1,b2,curve,E);
  edge(b2,b1,curve,A);
  edge(b1,b3,right,A);
  edge(b3,b2,right,AB);
  loop(b3,right,B);
\end{emp}
\\
\textbf{(a)} & \qquad\textbf{(b)}
\end{tabular}
\end{center}

\subsection*{Solution}

\end{empfile}
\immediate\write18{mpost -tex=latex \jobname}
\end{document}
