\ifx\AllTogetherMode\undefined%
\IfFileExists{../prefix.tex}%
{\input{../prefix}}%
{\input{prefix}}%
\fi

\HomeworkStart%
{3} % Homework number
{4} % Week of semester submitted
{2.5} % Version

\HWInstructionsStd{}%


%\SaveIndent%

\begin{questions}[start=7]
    \RestoreIndent%
    
    \medskip%
    \item \HWProblem{100}{Construct \NFAs}{%
		    \noindent For each of the following languages over $\Sigma = \{\Sym{3}, \Sym{7}, \Sym{4}\}$, 
	draw an \NFA that accepts them. Your \NFA should have a
       small number of states  (at most say 14 states). Provide
			 a brief explanation for your solution. 
       \begin{questions}%[(A)]
	
       \item \points{20} $\Sigma^* \Sym{3} \Sigma^* \Sym{7} \Sigma^* \Sym{4} \Sigma^* $
	
       \item \points{20} $\big (\Sym{3} (\Sym{3} + \Sym{7})^* \Sym{3} + \Sym{4} (\Sym{3} + \Sym{4})^* \Sym{4} + \Sym{7} (\Sym{4} + \Sym{7})^* \Sym{7}\big )^* $

       \item \points{20} All strings in $\Sigma^*$ that have a substring in $\Sym{3}\Sym{4}(\Sym{3}+\Sym{4}+\Sym{7})^2\Sym{7}$. 

 

       \item\label{Q1a} \points{20} All strings in $\Sigma^*$ that contain the substrings $\Sym{344}$ and $\Sym{443}$. 

	    \item \points{20} All strings in $\Sigma^*$ that satisfy at least one of the following:
	       \begin{itemize}
		       \item The number of times $\Sym{4}$ appears is divisible by 4.
			\item Every non-empty maximal substring of consecutive $\Sym{7}$s is odd.
			\item Every non-empty maximal substring of consecutive $\Sym{3}$s is divisible by 3.	
	       \end{itemize}
  
       \end{questions}
       
    }{}{}{}

    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    \bigskip%
    \item \HWProblem{100}{\DFAs to \NFAs}{%
      	
		\noindent    Given a \DFA $M = (\Sigma, Q, \delta, s, A)$ that accepts $L$, construct
			 an \NFA $N$ that accepts the following languages.  You can assume $\Sigma = \{\T0,\T1\}$ in~\ref{Q2A} and~\ref{Q2B}. Provide
			 a brief explanation for your solution.  	
		
		\begin{questions}
		\item  \label{Q2A} \points{25} $\emph{RemoveOnes}(L):= \Set{\T0^{\#_0(w)}}{w\in L}$; i.e., removes all $\T1$s from the strings. 

		\item \label{Q2B} \points{25} $\emph{RemoveOnes}^{-1}(L):= \Set{w \in \Sigma^*}{ \T0^{\#_0(w)}\in L}$; i.e., puts back the $\T1$s.


		\item \points{25} $\emph{Add-\Sym{k}-Ones}(L) :=$ inserts $k$ $\T1$s into the string. For example,  $\emph{Add-\Sym{3}-Ones}(L) := \Set{x\T1 y \T1 z \T1 w}{ xyzw \in L} $.  

		\item \points{25} $\emph{Substrings}(L) := \Set{y}{xyz \in L \text{ for some } x, y, z \in \Sigma^*}$; i.e., the language of all substrings of strings in $L$. For example, 
			if $L = \{\Sym{ABC} \}$, $\emph{Substrings}(L) = \{\epsilon, \Sym{A},\Sym{B}, \Sym{C}, \Sym{AB}, \Sym{BC}, \Sym{ABC} \}$. 





		\end{questions}
		    }{}{}{}
    
    
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
    \bigskip%
    \item \HWProblem{100}{Reg. Exp. to \NFA to \DFA}%
    {%
	\noindent	For each of the following regular expressions:
		\begin{enumerate}
			\item Construct an \NFA corresponding to the regular expression using Thompson's algorithm.
			\item Use the incremental subset construction to convert the \NFA to a \DFA
			\item Describe in natural english text the language defined by the regular expression.
			\item Create another DFA with at most say 4 states to recognize the language.
		\end{enumerate}


%(a) (ε+0)(1+10)∗ (b) 0∗(10∗10∗)∗


		\begin{questions}
		\item \points{50} $\T1^*\big(\T0\T1^*\T0\T1^*\big)^*\T0\T1^*$

		\item \points{50} $\big (\T1\T0 + \T0\big)^*(\T1 + \epsilon)$
		\end{questions}
      

	    }{}{}

\end{questions}


\HomeworkEnd{}