\documentclass[11pt, a4paper]{report}

\usepackage[brazil]{babel}
\usepackage[latin1]{inputenc}
\usepackage{fullpage}
\pagestyle{empty}
\usepackage{gastex}
\usepackage[usenames]{color}
\newcounter{conta}

\begin{document}

\vspace*{5mm}
\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2012 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Segunda Prova/Turma W} \hfill {\bf 08/05/2012}

\vspace*{3mm}
\noindent Cada questão vale 4 pontos.

\vspace*{3mm}
\begin{enumerate}
 \item Seja o AFN com o diagrama de estados a seguir:

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

        \drawedge[curvedepth=0](1,3){{\tt a}}
        \drawedge[curvedepth=0, ELside=r](2,3){{\tt a}}
        \drawedge[curvedepth=0](3,4){{\tt b},{\tt c}}
        \drawloop[loopangle=90](1){{\tt a},{\tt b}}
        \drawloop[loopangle=270](2){{\tt a},{\tt c}}
       \end{picture}

       Obtenha o diagrama de estados de um AFD equivalente usando o método visto em aula (\emph{subset construction}).

  \item Seja o AFN$\lambda$ com o diagrama de estados:

       \begin{picture}(120,40)
        \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}
        \node[Nmarks=ir, iangle=180](1)(20,20){1}
        \node(2)(35,30){2}
        \node(3)(35,10){3}
        \node(4)(50,20){4}
        \node[Nmarks=r,iangle=180](5)(70,20){5}

        \drawloop[loopangle=90](1){{\tt a}}
        \drawedge[curvedepth=0](1,2){$\lambda$}
        \drawedge[curvedepth=0,ELside=r](1,3){$\lambda$}
        \drawloop[loopangle=90](2){{\tt b}}
        \drawedge[curvedepth=0](2,4){{\tt a}}
        \drawloop[loopangle=270](3){{\tt c}}
        \drawedge[curvedepth=0,ELside=r](3,4){{\tt a}}
        \drawloop[loopangle=90](4){{\tt a}}
        \drawedge[curvedepth=0](4,5){$\lambda$}
        \drawloop[loopangle=0](5){{\tt b},{\tt c}}
       \end{picture}

       Obtenha o diagrama de estados de um AFN equivalente \textbf{utilizando o método visto em aula}.
       Para cada $(e,s)$ tal que $s\not=\lambda$ e $\delta'(e,s)\not=\delta(e,s)$ indique o c\'alculo de
       $\delta'(e,s)$. ($\delta$ é a função de transi\c{c}\~ao do AFN$\lambda$ e $\delta'$ a do AFN obtido.)

 \item Encontre expressões regulares que denotem:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $(\{{\tt 11}\}\cup\{{\tt 10}\}\{{\tt 00}\}^*\{{\tt 01}\})^*(\{{\tt 0},{\tt 11}\}\cup\{{\tt 10}\}\{{\tt 00}\}^*\{{\tt 1}\})$.
        \item $\{w\in\{{\tt 0},{\tt 1}\}^+\,|\,\eta(w) \textit{ mod } 3 = 1\}$, sendo $\eta(w)$ o número representado
              por $w$ na base 2.
       \end{list}

 \item Sejam as seguintes linguagens de alfabeto $\{{\tt 0},{\tt 1}\}$:
       \begin{itemize}
        \item $L_1=\{{\tt 0}\}^+\cup\{{\tt 1}\}^+$ (regular)
        \item $L_2=\{{\tt 0}\}^*\{{\tt 1}\}^*$ (regular)
        \item $L_3=\{{\tt 0}^n{\tt 1}^k \,|\, n\not=k\}$ (não regular)
       \end{itemize}
       Mostre que é regular ou que não é:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $L_1\cup L_3$. %Resp: não regular, pois L1 contida em L3; logo, (L1 U L3) = L3.
        \item $L_2\cup L_3$. %Resp: regular, pois L3 contida em L2; logo, (L3 U L2) = L2 .
       \end{list}
\end{enumerate}

\end{document}
