\documentclass[12pt]{article} \newcommand{\es}{\emptyset} \usepackage{tikz} \usetikzlibrary{automata,positioning,arrows} \begin{document} \newif{\ifshowsoln} \showsolntrue % comment out to NOT show solution inside \ifshowsoln and \fi blocks. \centerline{\bf Homework 2 Morally Due Feb 12} \begin{enumerate} \item (20 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. Give the diagram for a finite automata classifier that determines, given $w$, what $w$ is congruent to mod 6. How many states does it have? \item (30 points) We have seen some number $m$ such that the DECIDER (of minimal number of states) for Mod $m$ (is $x\equiv 0 \pmod m$) has LESS states than the CLASSIFIER (of minimal number of states) for mod $m$. \begin{enumerate} \item (15 points) Give an infinite number of examples of $m$, with $m\ge 100$, where the Decider will have LESS states than the classifier. Explain why this is, but you do not need to draw the DFA's. \item (15 points) Give an infinite number of examples of $m$, with $m\ge 100$, where the Decider will have AS MANY states as the classifier. Explain why this is, but you do not need to draw the DFA's. \item (0 points) Think about: Fill in the following statement: {\it The DECIDER for Mod $m$ will have LESS states than the CLASSIFIER iff XXX.} \end{enumerate} \item (25 points) Prove using NFA's: If $L$ is regular then $L^*$ is regular. Begin with an NFA for $L$ and then modify it to get an NFA for $L^*$. Formally write the new NFA in terms of the old one. Draw a picture also. \item (25 points) A JUSTIN-NFA is an NFA that has no e-transitions. Give a procedure that takes an NFA and produces an equivalent JUSTIN-NFA. (Note- be careful. A sequence of e-transitions can go through many states.) \end{enumerate} \end{document}