CS 418 Winter 24 Homework

HW_1.tex

\documentclass[12pt]{article}

\usepackage{fancyhdr}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{tikz}
\usepackage{comment}
\usepackage{enumitem}
\usepackage{xspace}

\newcommand{\ttzero}{\texttt{0}\xspace}
\newcommand{\ttone}{\texttt{1}\xspace}
\newcommand{\ttB}{\texttt{B}\xspace}
\newcommand{\ttR}{\texttt{R}\xspace}
\newcommand{\ttx}{\texttt{x}\xspace}

\usetikzlibrary{automata,positioning,arrows,arrows.meta}
\usetikzlibrary{shapes.geometric,fit}

\tikzset{node distance=2.5cm, % Minimum distance between two nodes. Change if necessary.
      every state/.style={ % Sets the properties for each state
      semithick,
      fill=gray!10},
      initial text={}, % No label on start arrow
      double distance=2pt, % Adjust appearance of accept states
      every edge/.style={ % Sets the properties for each transition
      draw,
      ->,>=stealth', % Makes edges directed with bold arrowheads
      auto,
      semithick}
}

\setlength{\headheight}{16pt}

\topmargin=-0.25in
\evensidemargin=0in
\oddsidemargin=0in
\textwidth=6.5in

\linespread{1.1}
\setlength\parindent{0pt}
\setlength{\parskip}{1em}


\pagestyle{fancy}
\chead{Theory of Computation: Homework 1}
\rhead{Version 1.1}

\begin{document}

For each exercise that asks for the formal definition of a DFA, you should
explicitly define each element of the 5-tuple; for the transition function
provide a table. Exercise 2 is a template that you can follow.

Do not use NFAs (Sipser section 1.2).

\begin{enumerate}
	\item{
	Provide the formal definition of the DFA that corresponds to the
	transition diagram shown below.

	\begin{tikzpicture}[shorten >=1pt,node distance=4cm,on grid,auto]
    \node[state,initial] (q_0) [] {$q_0$};
    \node[state] (q_1) [right=of q_0] {$q_1$};
    \node[state,accepting] (q_3) [right=of q_1] {$q_3$};
    \path[->]
        (q_0) edge [bend left] node {$\ttzero$} (q_1)
        (q_0) edge [loop above] node[align=left] {$\ttone$} (q_0)
        (q_1) edge [loop above] node[align=left] {$\ttone$} (q_1)
        (q_1) edge [bend left] node {$\ttzero$} (q_3)
        (q_3) edge [loop above] node[align=left] {$\ttzero,\ttone$} ()
        ;
    \end{tikzpicture}
	}

	\item{
	Draw the state transition diagram for the DFA $M = (Q, \Sigma,
	\delta, q_0, F)$ where $Q = \{ q_0, q_1, q_2, q_3 \}$, $\Sigma = \{c, d\}$,
	and $F = \{ q_1, q_3 \}$.
	The transition function $\delta$ is defined by the following table.

	\begin{center}
	\begin{tabular}{ c | c c }
	  & \texttt{c} & \texttt{d} \\
	 \hline
	 $q_0$ & $q_1$ & $q_2$ \\
	 $q_1$ & $q_2$ & $q_3$ \\
	 $q_2$ & $q_3$ & $q_2$ \\
	 $q_3$ & $q_3$ & $q_3$
	\end{tabular}
	\end{center}
	}
	\item{
		For each description of a language over the alphabet $\{\ttzero, \ttone\}$,  
		first give the formal definition of a DFA that recognizes the language,
		and then provide equivalent code using the syntax of the Doty simulator.
	}
	\begin{enumerate}
	    \item Strings that contain at least two \ttzero's or at least one \ttone.
	    \item \label{l} $\{ w \mid w$ does not contain the substring \texttt{111}$\}$.
	\end{enumerate}

    \vspace{0.15in}

	\item{
		Let $A$ be a regular language over the alphabet $\Sigma$. Assume 
		that \texttt{y} $\notin \Sigma$. Show, by construction of a DFA
		over the alphabet $\Sigma \cup \{\ttx\}$,
		that the language $L = \{ w\ttx  \mid w \in A \}$ is regular.
        That is, construct a DFA $M_L$ such that it accepts a string $w$ from $A$
        followed by a single $\ttx$. Try to do this without ChatGPT or Google.       
	}



\end{enumerate}



\end{document}

HW_2.tex

\documentclass[12pt]{article}

\usepackage{fancyhdr}
\usepackage{amsmath}
\usepackage{csquotes}
\usepackage{xspace}

\newcommand{\ttzero}{\texttt{0}\xspace}
\newcommand{\ttone}{\texttt{1}\xspace}
\newcommand{\tta}{\texttt{a}\xspace}
\newcommand{\ttb}{\texttt{b}\xspace}

\evensidemargin=0in
\oddsidemargin=0in
\textwidth=6.5in

\linespread{1.1}

\setlength{\headheight}{16pt}

\pagestyle{fancy}
\chead{Theory of Computation: Homework 2}
\rhead{Version 1.0}

\begin{document}

For each question that asks for Doty simulator code,
you should provide a single file named \texttt{hw2\_QUESTIONUM.doty} that contains your code.

\begin{enumerate}
  \item Let $A$ be the language of strings over the alphabet $\{\tta, \ttb\}$ that alternates symbols, i.e. where there are no instances of two $\tta$
  or two $\ttb$ symbols next to each other.
  For example, $\texttt{aba} \in A$, but $\texttt{aabba} \notin A$.
  The string $\texttt{b} \in A$, but $\texttt{aabba} \notin A$.
  \begin{enumerate}
    \item Write the formal definition of an NFA $N$ where $L(N) = A$.
    \item Provide equivalent code using the NFA syntax of the Doty simulator.
  \end{enumerate}
  \item Let $A = \{ x \in \{\ttzero,\ttone\}^* : x \text{ starts with \texttt{0} and ends with \texttt{0}} \}$ and $B = \{ x \in \{\ttzero,\ttone\}^* : x  \text{ start with \texttt{1} and ends with \texttt{1}} \}$.
  \begin{enumerate}
    \item Draw the state diagram of an NFA that recognizes $A \cup B$.
    \item Provide Doty simulator code for an NFA that recognizes $A \circ B$.
  \end{enumerate}

\item \textbf{Python NFA Implementation Exercise:} 
Extend the Python NFA implementation shown in class to recognize the following languages. 

\begin{enumerate}
    \item Language L1: $\{w \in \{0,1\}^* \mid w \text{ ends with \texttt{01}}\}$.
    \item Language L2: $\{w \in \{a,b\}^* \mid w \text{ contains the substring \texttt{aba}}\}$.
    \item Language L3: The complement of Language L2.
\end{enumerate}

\textbf{Instructions:}
\begin{itemize}
    \item Design an NFA for each language using the existing code. Fix bugs as necessary.
    \item Include comments in your code explaining your design choices.
    \item Test your NFAs with appropriate strings and include these test cases in your submission.
    \item \textbf{Use of AI Assistance for this question:} If you use ChatGPT or any other language model or generative AI tool for assistance, you must include a description of how it was used in solving the problem. The only unacceptable action is to misrepresent your use of AI. If you directly use AI-generated content, state so clearly; in such cases, the AI's output will be evaluated.
\end{itemize}
\textbf{Note:} Pay special attention to Language L3. Think creatively about how to represent the complement of a language in the context of NFAs.

\end{enumerate}
\end{document}