\documentclass[12pt, a4paper]{report}

\usepackage[brazilian]{babel}
\usepackage[T1]{fontenc} 
\usepackage{fullpage}

\usepackage{gastex}
\usepackage[usenames]{color}

\pagestyle{empty}
\newcounter{conta}

\begin{document}

%\vspace*{1cm}
\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2013 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Primeira Prova}/Solução do professor -- Turma W\hfill {04/4/2013}

\vspace*{3mm}
\begin{enumerate}
 \item {\footnotesize Qual linguagem abaixo difere das outras? Justifique sua resposta.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{0\}^*$
        \item $\{\lambda,0\}^*$
        \item $\{0\}^+$
        \item $\{\lambda,0\}^+$
       \end{list}}

       \emph{Solução}: $\{0\}^+$ difere das outras apenas no fato de que ela contém $\lambda$ e as outras não.

 \item {\footnotesize Seja $G$ a gramática de regras:
       \begin{quote}
        $P\,\rightarrow\, 0 P 1\,|\, \lambda$
       \end{quote}
       Em quantos passos (aplicações de regras) é derivada uma palavra $0^n1^n$? Justifique sua resposta.}

       \emph{Solução}: $P \,\stackrel{n}{\Rightarrow}\, 0^nP1^n \,\Rightarrow\, 0^n1^n$. Logo, $0^n1^n$ é
			 derivada em $n+1$ passos.

 \item {\footnotesize Descreva as linguagens a seguir, todas sobre o alfabeto $\{{\tt 0},{\tt 1}\}$,
       usando apenas \textit{conjuntos finitos} e opera\c{c}\~oes de \textit{uni\~ao}, \textit{interse\c{c}\~ao},
       \textit{complementa\c{c}\~ao}, \textit{concatena\c c\~ao} e \textit{fecho de Kleene}. Procure obter uma
       descri\c c\~ao bem concisa.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item O conjunto das palavras de prefixo {\tt 01}.
        \item O conjunto das palavras que n\~ao cont\^em {\tt 01} como sufixo.
			\end{list}}

       \emph{Solução}:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt 01}\}\{{\tt 0},{\tt 1}\}^*$.
        \item $\{\lambda,{\tt 1}\}\cup\{{\tt 0},{\tt 1}\}^*\{{\tt 0},{\tt 11}\}$. (outra solução: \overline{\{{\tt 0},{\tt 1}\}^*\{{\tt 01}\}})
			\end{list}

 \item {\footnotesize Construa AFDs para as linguagens da questão anterior.}

       \emph{Solução}:

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item \
				
				      \begin{picture}(50,12)
               \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}
               \node[Nmarks=i, iangle=180](1)(20,10){}
               \node(2)(40,10){}
               \node[Nmarks=r](3)(60,10){}

               \drawedge[curvedepth=0](1,2){\tt 0}
               \drawedge[curvedepth=0](2,3){\tt 1}
               \drawloop[loopangle=0](3){{\tt 0},{\tt 1}}
              \end{picture}
        \item \ 
				
				      \begin{picture}(50,20)
               \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}
               \node[Nmarks=ir, iangle=180](1)(20,15){}
               \node[Nmarks=r](2)(40,15){}
               \node(3)(60,15){}

               \drawloop[loopangle=90](1){{\tt 1}}
               \drawedge[curvedepth=0](1,2){\tt 0}
               \drawloop[loopangle=90](2){{\tt 0}}
               \drawedge[curvedepth=3](2,3){\tt 1}
               \drawedge[curvedepth=3](3,2){\tt 0}
               \drawedge[curvedepth=10](3,1){\tt 1}
              \end{picture}
			\end{list}

\pagebreak
 \item {\footnotesize Construa um AFD que reconheça $AB$, sendo:
			 \begin{itemize}
			  \item $A=\{w\in\{a,b\}^*\,|\, w \mbox{ tem número ímpar de $a$s}\}$, e
			  \item $B=\{w\in\{a,c\}^*\,|\, w \mbox{ tem número par de $a$s}\}$.
			 \end{itemize}
			 Comece construindo AFDs para $A$ e $B$; depois obtenha um AFN$\lambda$ para $AB$ a partir dos dois; em seguida
			 transforme o AFN$\lambda$ em AFN; e, finalmente, obtenha o AFD a partir do AFN.}

       \emph{Solução}:
			
{\small
       \begin{picture}(50,20)(-10,0)
        \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}
        \node[Nmarks=i, iangle=180](1)(20,10){1}
        \node[Nmarks=r](2)(40,10){2}

        \put(10,10){\makebox(0,0)[r]{$A$:}}
        \drawloop[loopangle=90](1){$b$}
        \drawedge[curvedepth=3](1,2){$a$}
        \drawloop[loopangle=90](2){$b$}
        \drawedge[curvedepth=3](2,1){$a$}
       \end{picture}
       \begin{picture}(60,20)
        \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}
        \node[Nmarks=ir, iangle=180](3)(20,10){3}
        \node(4)(40,10){4}

        \put(10,10){\makebox(0,0)[r]{$B$:}}
        \drawloop[loopangle=90](3){$c$}
        \drawedge[curvedepth=3](3,4){$a$}
        \drawloop[loopangle=90](4){$c$}
        \drawedge[curvedepth=3](4,3){$a$}
       \end{picture}


       \begin{picture}(50,20)(-10,0)
        \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}
        \node[Nmarks=i, iangle=180](1)(20,10){1}
        \node(2)(40,10){2}

        \put(10,10){\makebox(0,0)[r]{AFN$\lambda$:}}
        \drawloop[loopangle=90](1){$b$}
        \drawedge[curvedepth=3](1,2){$a$}
        \drawloop[loopangle=90](2){$b$}
        \drawedge[curvedepth=3](2,1){$a$}

        \node[Nmarks=r](3)(60,10){3}
        \node(4)(80,10){4}

        \drawedge[curvedepth=0](2,3){$\lambda$}

        \drawloop[loopangle=90](3){$c$}
        \drawedge[curvedepth=3](3,4){$a$}
        \drawloop[loopangle=90](4){$c$}
        \drawedge[curvedepth=3](4,3){$a$}
       \end{picture}

       \begin{picture}(50,20)(-10,0)
        \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}
        \node[Nmarks=i, iangle=180](1)(20,10){1}
        \node(2)(40,10){2}

        \put(10,10){\makebox(0,0)[r]{AFN:}}
        \drawloop[loopangle=90](1){$b$}
        \drawedge[curvedepth=3](1,2){$a$}
        \drawloop[loopangle=90](2){$b$}
        \drawedge[curvedepth=3](2,1){$a$}

        \node[Nmarks=r](3)(60,10){3}
        \node(4)(80,10){4}

        \drawedge[curvedepth=-10](1,3){$a$}
        \drawedge[curvedepth=0](2,3){$b$}

        \drawloop[loopangle=90](3){$c$}
        \drawedge[curvedepth=3](3,4){$a$}
        \drawloop[loopangle=90](4){$c$}
        \drawedge[curvedepth=3](4,3){$a$}
       \end{picture}

       \begin{picture}(50,35)(-10,0)
        \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}
        \node[Nmarks=i, iangle=180](1)(20,12.5){1}
        \node[Nmarks=r](23)(40,20){23}
        \node(14)(40,5){14}
        \node[Nmarks=r](3)(60,20){3}
        \node(4)(60,5){4}
 
        \put(10,12.5){\makebox(0,0)[r]{AFD:}}

        \drawloop[loopangle=90](1){$b$}
        \drawedge[curvedepth=0](1,23){$a$}
        \drawloop[loopangle=90](23){$b$}
        \drawedge[curvedepth=3](23,14){$a$}
        \drawedge[curvedepth=0](23,3){$c$}
        \drawedge[curvedepth=0](14,4){$c$}
        \drawedge[curvedepth=3](14,23){$a$}
        \drawedge[curvedepth=0](14,1){$b$}
        \drawloop[loopangle=90](3){$c$}
        \drawedge[curvedepth=3](3,4){$a$}
        \drawloop[loopangle=270](4){$c$}
        \drawedge[curvedepth=3](4,3){$a$}
       \end{picture}
}
\end{enumerate}

\end{document}
