\documentclass[11pt, a4paper]{report}

\usepackage[portuguese]{babel}
\usepackage{fullpage}
\pagestyle{empty}
\newcounter{conta}
\usepackage{gastex}
\usepackage[usenames]{color}

\begin{document}

\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2007 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Primeira Prova} \hfill {27/03/2007}

\vspace*{1mm}
\noindent \textbf{Dura\c{c}\~ao:} 1 hora e 30 minutos. \\
\noindent \textbf{Valor de cada quest\~ao:} 3 pontos.

\vspace*{2mm}
\begin{enumerate}

 \item Sejam $A=\{{\tt a}\}$ e $B=\{{\tt bb}\}$. Quantas palavras de $n$
       s\'{\i}mbolos, para cada $n\geq 0$, h\'a em:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $A^*B$?
        \item $AB^*$?
        \item $A^*B^*$?
       \end{list}

 \item Obtenha gram\'aticas para as seguintes linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt 0},{\tt 1}\}^*\{{\tt 00},{\tt 11}\}$.
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\,$ o n\'umero de {\tt 0}s em $w$ \'e
              \'{\i}mpar$\}$.
        \item $\{wxw^R\,|\, w\in\{{\tt a},{\tt b}\}^* \mbox{ e } x\in\{\tt c\}^*\}$.
       \end{list}

 \item Construa AFDs que reconhe\c cam
       as linguagens a seguir. Apresente apenas os diagramas de estados.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt ab}\}^*\{{\tt aba}\}$.
        \item $\{w\in\{{\tt a},{\tt b},{\tt c}\}^*\,|\,$ a subpalavra {\tt abc}
               ocorre um n\'umero \'{\i}mpar de vezes em $w\}$.
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, w$ cont\'em o mesmo s\'{\i}mbolo
              em todas as posi\c{c}\~oes \'{\i}mpares$\}$. Considere que o primeiro
              s\'{\i}mbolo da palavra est\'a na posi\c{c}\~ao 1, o segundo na
              posi\c{c}\~ao 2 etc.
       \end{list}

 \item Sejam os AFDs $M_1$ e $M_2$ com os diagramas de estado mostrados
       a seguir.

       \begin{picture}(100,40)
        \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}
        \put(10,30){\makebox(0,0){$M_1$:}}
        \node[Nmarks=i, iangle=180](a)(30,30){a}
        \node[Nmarks=r](b)(50,30){b}
        \node(c)(70,30){c}

        \put(10,10){\makebox(0,0){$M_2$:}}
        \node[Nmarks=ir, iangle=180](1)(30,10){1}
        \node(2)(50,10){2}

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

       Observe que o diagrama de $M_1$ \'e o simplificado.
       Obtenha o diagrama de estados do produto de $M_1$ e $M_2$. Explicite
       quais seriam os estados finais para um AFD que reconhe\c{c}a:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $L(M_1)\cup L(M_2)$.
        \item $L(M_1)\cap L(M_2)$.
       \end{list}

 \item A diferen\c{c}a sim\'etrica de duas linguagens $A$ e $B$ \'e
       $C=(A\cup B)-(A\cap B)$.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Explique como obter um AFD $M_3$, a partir de AFDs $M_1$ e
              $M_2$, que reconhe\c{c}a a diferen\c{c}a sim\'etrica de 
              $L(M_1)$ e $L(M_2)$.
        \item \'E poss\'{\i}vel saber se $L(M_1)=L(M_2)$, analisando-se o
              AFD $M_3$. Como?
       \end{list}
\end{enumerate}

\noindent \textbf{Extra.} Demonstre qualquer uma das respostas da primeira
quest\~ao, usando indu\c{c}\~ao matem\'atica, e ganhe um ponto extra!

\end{document}
