\documentclass[11pt, a4paper]{report}

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

\begin{document}

\vspace*{10mm}
\noindent {\it Fundamentos da Teoria da Computação}
\hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2011 \\
\noindent Professor: Newton José Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Primeira Prova}/Turma W/Solução do professor \hfill {7/4/2011}

\begin{enumerate}

 \item {\footnotesize Seja $\Sigma=\{{\tt a},{\tt b},{\tt c}\}$ e sejam as seguintes linguagens de alfabeto $\Sigma$:
       $L_1=\{{\tt a},{\tt b}\}^*\{{\tt c}\}\{{\tt a},{\tt b}\}^*$ e $L_2=\{{\tt c}\}\{{\tt a},{\tt b}\}^*$.
       Para cada linguagem a seguir, escreva uma condição necessária e suficiente para
       que uma palavra pertença a ela, supondo que o alfabeto é $\Sigma$:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $L_1L_2$.
        \item $\overline{L_1}\cup L_2$.
       \end{list}
       Exemplo: uma condição necessária e suficiente para que uma palavra pertença a $L_1L_1$ é \emph{
       contém exatamente dois {\tt c}s.}}

       \emph{Solução:}

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Contém exatamente dois {\tt c}s.
        \item Se contiver um único {\tt c}, ele é seu primeiro símbolo.
       \end{list}

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

       \emph{Solução:}

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt 1}\}^*\{{\tt 0}\}\{{\tt 1}\}^*\{{\tt 0},\lambda\}\{{\tt 1}\}^*$
        \item $\{\lambda,{\tt 0}\}\cup\{{\tt 00},{\tt 1}\}\{{\tt 0},{\tt 1}\}^*$
       \end{list}

 \item {\footnotesize Obtenha gram\'aticas para as seguintes linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item O conjunto das palavras com um ou dois {\tt 0}s (não necessariamente consecutivos).
        \item $\{xyx^R \,|\, x\in\{{\tt a},{\tt b}\}^* \mbox{ e } y\in\{{\tt c}{\tt c}\}^*\}$.
       \end{list}}

       \emph{Solução:}

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $P \,\rightarrow\, X{\tt 0}X \,|\, X{\tt 0}X{\tt 0}X$ \\
              $X \,\rightarrow\, {\tt 1}X \,|\, \lambda$ \\
        \item $P \,\rightarrow\, {\tt a}P{\tt a} \,|\, {\tt b}P{\tt b} \,|\, C$ \\
              $C \,\rightarrow\, {\tt c}C{\tt c} \,|\, \lambda$ \\
       \end{list}

 \item {\footnotesize Construa AFDs que reconhe\c cam as linguagens a seguir.
       Apresente apenas os diagramas de estados (que podem ser simplificados).
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item O conjunto das palavras de $\{{\tt 0},{\tt 1}\}^*$ com um ou dois {\tt 0}s 
              (não necessariamente con\-se\-cu\-tivos).
        \item $\{{\tt a},{\tt b}\}^*\{\lambda,{\tt c}\}\{{\tt a},{\tt b}\}^*$.
        \item O conjunto das palavras de $\{{\tt 0},{\tt 1}\}^*$ com número par de {\tt 1}s,
              mas nenhum {\tt 11}.
       \end{list}}

       \emph{Solução:}

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item  \ 
        
              \mbox{\setlength{\unitlength}{1mm}
       \begin{picture}(100,15)
        \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}

        \node[Nmarks=i, iangle=180](1)(25,10){}
        \node[Nmarks=r](2)(45,10){}
        \node[Nmarks=r](3)(65,10){}

        \drawloop[loopangle=90](1){{\tt 1}}
        \drawedge[curvedepth=0](1,2){{\tt 0}}
        \drawloop[loopangle=90](2){{\tt 1}}
        \drawedge[curvedepth=0](2,3){{\tt 0}}
        \drawloop[loopangle=90](3){{\tt 1}}
       \end{picture}
}
        \item  \ 
        
              \mbox{\setlength{\unitlength}{1mm}
       \begin{picture}(100,15)
        \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}

        \node[Nmarks=ir, iangle=180](1)(25,10){}
        \node[Nmarks=r](2)(45,10){}

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

        \item  \ 
        
              \mbox{\setlength{\unitlength}{1mm}
       \begin{picture}(100,32)
        \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}

        \node[Nmarks=ir, iangle=180](1)(25,25){}
        \node[Nmarks=r](2)(45,25){}
        \node(3)(25,10){}
        \node(4)(45,10){}

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

       \end{list}


 \item {\footnotesize Seja $\Sigma=\{{\tt}0,{\tt 1}\}$ e:
       \begin{itemize}
        \item $X=\{{\tt 0}\}\Sigma^*$
        \item $Y=\Sigma^*\{{\tt 01}\}\Sigma^*$.
       \end{itemize}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Desenhe os diagramas de estados de AFDs que reconhe\c{c}am $X$ e $Y$. O que reconhece $X$ deve ter
              dois estados e o que reconhece $Y$ deve ter três estados.
        \item Obtenha o diagrama de estados para o produto dos dois AFDs e diga quais s\~ao os estados finais
              para reconhecer $X\cap Y$ e $X\cup Y$.
       \end{list}}

       \emph{Solução:}

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item  \ 
        
              \mbox{\setlength{\unitlength}{1mm}
       \begin{picture}(100,30)
        \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}

        \node[Nmarks=i, iangle=180](a)(20,10){a}
        \node[Nmarks=r](b)(40,10){b}
        \node(c)(20,25){c}

        \drawedge[curvedepth=0](a,b){{\tt 0}}
        \drawedge[curvedepth=0](a,c){{\tt 1}}
        \drawloop[loopangle=0](b){{\tt 0},{\tt 1}}
        \drawloop[loopangle=0](c){{\tt 0},{\tt 1}}

        \node[Nmarks=i, iangle=180](1)(80,10){1}
        \node(2)(100,10){2}
        \node[Nmarks=r](3)(120,10){3}

        \drawloop[loopangle=90](1){{\tt 1}}
        \drawedge[curvedepth=0](1,2){{\tt 0}}
        \drawloop[loopangle=90](2){{\tt 0}}
        \drawedge[curvedepth=0](2,3){{\tt 1}}
        \drawloop[loopangle=90](3){{\tt 0},{\tt 1}}
       \end{picture}
}
        \item  \ 
        
              \mbox{\setlength{\unitlength}{1mm}
       \begin{picture}(100,30)
        \gasset{Nw=8, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}

        \node[Nmarks=i, iangle=180](a1)(20,25){a1}
        \node(b2)(40,25){b2}
        \node(b3)(60,25){b3}
        \node(c1)(20,10){c1}
        \node(c2)(40,10){c2}
        \node(c3)(60,10){c3}

        \drawedge[curvedepth=0](a1,b2){{\tt 0}}
        \drawedge[curvedepth=0](a1,c1){{\tt 1}}
        \drawloop[loopangle=90](b2){{\tt 0}}
        \drawedge[curvedepth=0](b2,b3){{\tt 1}}
        \drawloop[loopangle=0](b3){{\tt 0},{\tt 1}}
        \drawloop[loopangle=270](c1){{\tt 1}}
        \drawedge[curvedepth=0](c1,c2){{\tt 0}}
        \drawloop[loopangle=90](c2){{\tt 0}}
        \drawedge[curvedepth=0](c2,c3){{\tt 1}}
        \drawloop[loopangle=0](c3){{\tt 0},{\tt 1}}
       \end{picture}
}
 \item Estados finais para reconhecer $X\cap Y$: $\{\mbox{b3}\}$. \\
       Estados finais para reconhecer $X\cup Y$: $\{\mbox{b2},\mbox{b3},\mbox{c3}\}$.
\end{list}
\end{enumerate}

\end{document}
