\documentclass[12pt]{article} \usepackage{tikz} \usetikzlibrary{automata,positioning,arrows} \usepackage{amsmath} \begin{document} \newif{\ifshowsoln} \showsolntrue % comment out to NOT show solution inside \ifshowsoln and \fi blocks. \centerline{\bf Homework 1 Morally Due Feb 11} {\bf WARNING: THIS HW IS TWO PAGES LONG!!!!!!!!!!!!!!!!!!!!!} \begin{enumerate} \item (0 points, but if you actually miss the midterm without telling Dr. Gasarch ahead of time, you will lose 100 points on this homework) When will the midterm be (give date and time)? When will the final be (give date and time)? By when do you have to tell Dr.\ Gasarch that you cannot make the midterm? % For reference: % Midterm is on Tuesday, March 31, in class % Final is on Thursday, May 14, 8AM - 10AM % Must tell Bill by Feb 11 in both cases \item (0 points, but if you miss emails related to the course, you can't complain) If you are not getting emails that the class gets, then email Saadiq, Josh, and Dr. Gasarch as soon as possible. You should have gotten an email saying this homework was posted. % Problem 3 \item (35 points) The alphabet is $\{0,\ldots,9\}$. We interpret the input as a base 10 natural number, read \emph{right to left}. So the number 29139 will be read 9-3-1-9-2. \begin{enumerate} \item (10 points) Compute $10^0 \pmod {13}$ $10^1 \pmod {13}$ $10^2 \pmod {13}$ etc. until you spot a pattern. What is the pattern? \item (25 points) Give a DFA classifier that determines, given a number in base 10, what that number is congruent to mod 13. Include \begin{itemize} \item $Q$, the state set \item $\delta$, the transition function, \textbf{give a table not a diagram!}, the table should state how $\delta$ operates given the running sum and the position \item For each $0 \le a \le 12$, the set $F_a$ of states that a number congruent to $a$ (mod 13) will end up in. \item (We're not asking you for the alphabet because we know it's $\{0, ..., 9\}$). \end{itemize} \end{enumerate} \textbf{More Homework on Next Page!} \newpage % Problem 5 \item (35 points) We define $\#_a(w)$ to be the number of $a$'s in $w$. The alphabet is $\{a, b\}$. \begin{enumerate} \item (15 points) Draw a DFA for $\{w \mid \#_a(w) \equiv 0,1 \pmod{4}\}$. How many states does this DFA have? \item (20 points) Draw a DFA for $\{w \mid \#_a(w) \equiv 0,2 \pmod{4}\}$. How many states does this DFA have? (Hint: this should be less states than the prior part.) \end{enumerate} % Problem 6 \item (30 points) The alphabet for this problem is $\{a, b\}$. \begin{enumerate} \item (7 points) Draw an NFA for the language $\Sigma^*aa\Sigma^*$. Try to make the number of states as small as possible. How many states does it have? \textbf{For your own benefit do an NFA for $\Sigma^*a^3\Sigma^*$}. \item (7 points) Draw a DFA for the language $\Sigma^*aa\Sigma^*$. Use the NFA from part (a). Try to make the number of states as small as possible. How many states does it have? \textbf{For your own benefit do a DFA for $\Sigma^*a^3\Sigma^*$}. \item (8 points) Draw an NFA for the language $\Sigma^*a^n\Sigma^*$. Try to make the number of states as small as possible. Use "..." to specify a certain number of states. How many states does it have as a function of $n$? \item (8 points) Draw a DFA for the language $\Sigma^*a^n\Sigma^*$. Use the NFA from part (e). Try to make the number of states as small as possible. Use "..." to specify a certain number of states. How many states does it have as a function of $n$? \end{enumerate} \end{enumerate} \end{document} %%% Local Variables: %%% mode: latex %%% TeX-master: t %%% End: