\documentclass[]{article}
% Required packages.
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage{amssymb,amsmath}
\usepackage{color}
\usepackage{tikz}
\usepackage[utf8]{inputenc}
\usepackage{dsfont}
% Some setup.
\setlength{\parindent}{0pt}
\setlength{\parskip}{6pt plus 2pt minus 1pt}
\setlength{\emergencystretch}{3em} % prevent overfull lines
\setcounter{secnumdepth}{0}
% Input data macros for \maketitle.
\title{CS 4810: Homework 2}
\author{due 09/12 midnight}
\date{(your name + netid)} % TODO: Fill in your own name and netID here.
% The actual document technically begins here.
\begin{document}
\maketitle
Collaborators: (names and netids) % TODO: List the names and netIDs of everyone who collaborated with you on this homework here.
Each problem is worth 20 points.
\section{Problem 1}
Show that a Boolean function can be represented by a straight-line program of length
at most $\ell$ if and only if it can be represented by a Boolean circuit
of size at most $\ell$. (See the
lecture notes for the definition of a straight-line program.)
\section{Problem 2}
Show that every finite subset of $\{0,1\}^\ast$ is the language accepted by some DFA.
\section{Problem 3}
For reasons unknown, a man is travelling with a wolf, a goat and a very large cabbage. He is faced with unforeseen difficulties when he finds his path blocked by a roaring river, which may only be crossed by using a small boat tied to the shore. Indeed, the boat is so small that he can only possibly take one of his possessions (the cabbage is not to be taken lightly) on it at a time. Furthermore, his animal companions are proving less than cooperative and it is evident that neither the wolf and the goat nor the goat and the cabbage can be left ashore together without bipedal supervision, lest an undesirable \textit{consumption event} occur.
Give a DFA that characterises the problem, with an appropriately chosen alphabet of possible actions for the traveller to take. By looking at your DFA or otherwise, find a sequence of actions that solves the conundrum.
\section{Problem 4}
Construct a DFA that accepts exactly the following language: \[
L_{\text{odd}} = \{ x\in\{0,1\}^\ast \mid \text{$x$ contains an odd number of $0$'s and an odd number of $1$'s}\}.
\]
\section{Problem 5}
\begin{tabular}{lp{13cm}}
(\textit{a}) & Construct a DFA for the following language: \[
L_7=\{x\in \{0,1\}^* \mid \text{$x$ is the binary encoding of a multiple of $7$}\}.
\] \\
(\textit{b}) & Sketch a proof that, in fact, for any $m,k\in \mathds{N}$, $k>1$, the language \[
L_{m,k}=\{x\in \{0,1,\ldots,k-1\}^* \mid \text{$x$ is the base-$k$ encoding of a multiple of $m$}\}
\] has a DFA. \\
\end{tabular}
\end{document}