%
% Assignment 1a 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 1a} \\[2mm]
Fall 2024

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

\raggedright

\section*{Exercise 1.6bcefm (15 points)}

\subsection*{Problem}

Give state diagrams of DFAs recognizing the following languages. In
all parts the alphabet is $\{0,1\}$.

\begin{itemize}
\item[a.] \textit{Example} Language: $\{w|w$ begins with a $1$ and ends with a $0 \}$

\textbf{Solution}

\begin{center}
\begin{emp}(0,0)
  mediumnodes;
  u := 1.5cm;
  node.a0(); a0.c=origin;
  node.a1(); a1.c=a0.c shifted (u,0);
  node.a2(); a2.c=a1.c shifted (u,0);
  node.a3(); a3.c=a0.c shifted (0,-u);
  makestart(a0);
  makefinal(a2);
  drawboxed(a0,a1,a2,a3);
  edge(a0,a1,left,ONE);
  edge(a0,a3,left,ZERO);
  edge(a1,a2,curve,ZERO);
  loop(a1,up,ONE);
  edge(a2,a1,curve,ONE);
  loop(a2,up,ZERO);
  loop(a3,right,ZEROONE);
\end{emp}
\end{center}

\item[b.] Language: $\{w|w$ contains at least three $1$s$\}$

\textbf{Solution}

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

\textbf{Solution}

\item[e.] Language: $\{w|w$ starts with $0$ and has odd length, or
starts with $1$ and has even length$\}$

\textbf{Solution}

\item[f.] Language: $\{w|w$ doesn't contain the substring $110\}$

\textbf{Solution}

\item[m.] Language: The empty set

\textbf{Solution}
\end{itemize}

\section*{Exercise 1.7c (5 points)}

\subsection*{Problem}

Give state diagrams of NFAs with the specified number of states
recognizing each of the following languages. In all parts the
alphabet is $\{0,1\}$.

\begin{itemize}
\item[c.] Language: $\{w|w$ contains an even number of $0$'s, or
contains exactly two $1$s$\}$ with six states
\end{itemize}

\subsection*{Solution}

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