\documentclass[12pt]{article} \newcommand{\es}{\emptyset} \newcommand{\st}{\mathrel{:}} \newcommand{\e}{\varepsilon} \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 18 at 11:00 AM} \centerline{\bf THIS HOMEWORK IS THREE 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, or if you are not on Piazza, then email Saadiq, Josh, and Dr. Gasarch as soon as possible. \bigskip \centerline{\bf GOTO NEXT PAGE FOR MORE HOMEWORK} \newpage \item (40 points) The alphabet is $\{a\}$. For $p$ prime let $$L_p=\{a^i \st i\equiv 0 \pmod{p}\}.$$ \begin{enumerate} \item (10 points) Describe a DFA for $L_2 \cup L_3 \cup L_5 \cup L_7$ by giving $(Q,\delta,s,F)$. $\delta$ should be described by a table. How many states does the DFA have? How many final states does it have? Hint: the DFA has a short description. \item (10 points) Describe an NFA for $L_2 \cup L_3 \cup L_5 \cup L_7$ by giving $(Q,\Delta,s,F)$. $\Delta$ should be described by a table. How many states does the NFA have? How many final states does it have? Hint: the NFA has a short description. Try to make the NFA have less states than the DFA. You might fail. \item (10 points) Describe a DFA for $L_2 \cap L_3 \cap L_5 \cap L_7$ by giving $(Q,\delta,s,F)$. $\delta$ should be described by a table. How many states does the DFA have? How many final states does it have? Hint: the DFA has a short description. \item (10 points) Describe an NFA for $L_2 \cap L_3 \cap L_5 \cap L_7$ by giving $(Q,\Delta,s,F)$. $\Delta$ should be described by a table. How many states does the NFA have? How many final states does it have? Hint: the NFA has a short description. Try to make the NFA have less states than the DFA. You might fail. \item (0 points) Think about: (1) are the DFAs in parts (a) and (c) optimal? (2) What about DFAs and NFAs for $L_2 \cup L_3 \cup L_5\cup \cdots \cup L_{p_k}$ where $p_k$ is the $k$th prime? (3) What about DFAs and NFAs for $L_2 \cap L_3 \cap L_5 \cap \cdots \cap L_{p_k}$ where $p_k$ is the $k$th prime? \end{enumerate} \centerline{\bf GOTO NEXT PAGE FOR MORE HOMEWORK} \newpage \item (30 points) Let $w^R$ be the reverse of $w$ and let $L^R = \{w : w^R \in L\}$. Prove that if $L$ is regular then $L^R$ is regular. Fill in the following: If the DFA for $L$ has $n$ states, then the DFA for $L^R$ has $XXX(n)$ states. What is $XXX$? \item (30 points) A SAADIQ-NFA is an NFA that has no $\e$-transitions. Give a procedure that takes an NFA and produces an equivalent SAADIQ-NFA. (Note - be careful. A sequence of $\e$-transitions can go through many states.) \end{enumerate} \end{document}