% Author Info
\def\thetitle{HW6 Automata}
\def\theclass{CS105}
\def\university{University of Massachusetts Boston}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% You can ignore all this stuff for now
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\documentclass[12pt,letterpaper]{article}

\usepackage{amsmath,amsfonts,amsthm,amssymb}
\usepackage{setspace}
\usepackage{Tabbing}
\usepackage{lastpage}
\usepackage{extramarks}
\usepackage{chngpage}
\usepackage{soul,color}
\usepackage{graphicx,float,wrapfig}
\usepackage[ruled,vlined,linesnumbered]{algorithm2e}
\usepackage{url}
\usepackage{scalefnt}
%Tikz
\usepackage{tikz}
\usetikzlibrary{trees,snakes}
\usetikzlibrary{arrows,automata}
\usetikzlibrary{matrix}
\usetikzlibrary{calc}
\usetikzlibrary{positioning}
\usetikzlibrary{chains,positioning,scopes}

\usepackage{circuitikz}

\usepackage{multicol}


\setlength{\parskip}{0pt} % 1ex plus 0.5ex minus 0.2ex}
\setlength{\parindent}{0pt}

% Increase to 2.0 for double spacing.
\linespread{1}

% Header & Footers
% LaTeX has very generous margins, by default.
% I've shrunk the margins, considerably.
\usepackage[hmargin=2cm,vmargin=3.5cm]{geometry}
\usepackage{fancyhdr}
\pagestyle{fancy}
\lhead{\thetitle}
\chead{}
\rhead{\theclass}
\lfoot{}
\cfoot{}
\rfoot{\thepage}
\renewcommand{\headrulewidth}{0.5pt}
\renewcommand{\footrulewidth}{0.5pt}

\begin{document}




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% You work below this part
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% $\lnot \Box$
% 
% $\diamondsuit$
% 
% $\bigcirc$

Name:
\vspace{30pt}

1. RECAP: What values of (a,b,c,d) make this logic circuit output a false value?


\begin{center}
\vspace{30pt}
\begin{circuitikz} 


\node (a) at (0,0) {$a$};
\node (b) at (0,-1) {$b$};
\node (c) at (0,-2) {$c$};
\node (d) at (0,-3) {$d$};


\draw
(3,-0.5) node[and port] (and1) {}
(3,-2.5) node[or port] (or1) {}
(5,-2) node[and port] (and2) {}
(7,0) node[xnor port] (xnor) {}

(and1.out) -- (xnor.in 1)
(and2.out) -- (xnor.in 2)
(or1.out) -- (and2.in 2);

\draw (a) -- (and1.in 1);
\draw (b) -- (and1.in 2);

\draw (b) -- (or1.in 1);
\draw (d) -- (or1.in 2);

\draw (c) -- (and2.in 1);
\end{circuitikz}

\end{center}









\newpage 

2. Describe in words or in a regular expression what strings this automata will
accept. You can write each word in parentheses like $(Hello)$ so you can treat
it like a single character.



\begin{center}
\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node
distance=2.8cm,semithick] 
  \tikzstyle{final}=[circle,thick,draw=blue!75,fill=blue!20,text=black] 
  \node[initial,state] 	(1)                    	{$q_1$}; 
  \node[state]   		(2) [right of=1] 	  	{$q_2$};
  \node[state]   		(3) [right of=2] 	  	{$q_3$};
  \node[state, final]   (4) [right of=3] 	  	{$q_4$};
  \node[state]   		(5) [below of=3] 	  	{$q_5$};
	
  \path (1) edge [loop above] 	node {$Hello,$} (1)
            edge              	node {$how$} (2)
        (2) edge  		      	node {$are$} (3)
        (3)	edge			 	node {$you$} (4)
        (3)	edge 			 	node {$you!$} (5)
        (4)	edge [loop above]	node {$today?$} (4)
        ;
\end{tikzpicture}
\end{center}


\newpage 

3. Write an automata that will accept strings starting with an $R$ and then
followed by zero or more $h$'s. Such as $R$, $Rh$, $Rhh$,\ldots



\newpage 

4. Describe what the $HALT(\#_p,x)$ program could do if anyone could every write it.



\end{document}