\documentclass[12pt]{article} \usepackage{tikz} \usetikzlibrary{automata,positioning,arrows} \newcommand{\lf}{\left\lfloor} \newcommand{\rf}{\right\rfloor} \newcommand{\lc}{\left\lceil} \newcommand{\rc}{\right\rceil} \newcommand{\Ceil}[1]{\left\lceil {#1}\right\rceil} \newcommand{\ceil}[1]{\left\lceil {#1}\right\rceil} \newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor} \newcommand{\N}{{\sf N}} \newcommand{\st}{\mathrel{:}} \newcommand{\nth}{n^{th}} \newcommand{\es}{\emptyset} \begin{document} \newif{\ifshowsoln} \showsolntrue % comment out to NOT show solution inside \ifshowsoln and \fi blocks. \centerline{\bf Homework 5 Morally Due Mar 12 at 11:00 AM, Dead Cat March 31} \centerline{\bf THIS HOMEWORK 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 \centerline{\bf GOTO NEXT PAGE} \newpage \item (100 points) For this problem you may use the following theorem. \noindent {\bf Theorem:} If $x,y$ are relatively prime then \begin{itemize} \item For all $z\ge xy-x-y+1$ there exists $c,d\in\N$ such that $z=cx+dy$. \item There is no $c,d\in\N$ such that $xy-x-y=cx+dy$. \end{itemize} The alphabet is $\{a\}$. Let $$L = \{ a^n : n\ne 160 \}$$ {\bf WAITING:} Do not use the Pumping Lemma for this problem. e are NOT asking if $L$ is regular (it is!) we are asking about the number of states for a DFA for $L$ and an NFA for $L$. \begin{enumerate} \item (30 points) Does there exist a DFA for $L$ with $\le 159$ states? If so then draw the DFA; you may use DOT DOT DOT (You DO NOT have to prove that it works.) If not then PROVE there is no such DFA. \item (30 points) Does there exist a DFA for $L$ with $\le 160$ states? If so then draw the DFA; you may use DOT DOT DOT (You DO NOT have to prove that it works.) If not then PROVE there is no such DFA. \item (40 points) Does there exist an NFA for $L$ with $\le 50$ states? If so then draw the NFA; you may use DOT DOT DOT (You DO NOT have to prove that it works.) If not then PROVE there is no such NFA. \end{enumerate} \end{enumerate} \end{document}