\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 N/Solução do professor \hfill {7/4/2011}

\begin{enumerate}

 \item {\footnotesize Seja $\Sigma=\{{\tt 0},{\tt 1},{\tt 2}\}$ e sejam as seguintes linguagens de alfabeto $\Sigma$:
       $L_1=\{{\tt 0},{\tt 1}\}\{{\tt 0},{\tt 1}\}^*$ e $L_2=\{{\tt 1}\}\{{\tt 1},{\tt 2}\}^*$.
       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_2L_2$.
        \item $L_1\cap 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 no mínimo dois símbolos e não contém {\tt 2}.}}

       \emph{Solução:}

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Começa com {\tt 1}, contém no mínimo mais um {\tt 1} e não contém {\tt 0}s.
        \item Contém apenas {\tt 1}s, no mínimo um 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 $\{{\tt 0}{\tt 1}^i{\tt 0}\,|\, i \mbox{ é ímpar}\}$.
        \item O conjunto das palavras no alfabeto $\Sigma=\{{\tt a},{\tt b},{\tt c}\}$ da forma $xyz$, em que $x$
              não contém {\tt a}, $y$ não contém {\tt b} e $z$ contém apenas {\tt c}s (um ou mais).
       \end{list}}

       \emph{Solução:}

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt 01}\}\{{\tt 11}\}^*\{{\tt 0}\}$
        \item $\{{\tt b},{\tt c}\}^*\{{\tt a},{\tt c}\}^*\{{\tt c}\}^+$
       \end{list}

 \item {\footnotesize Obtenha gram\'aticas para as seguintes linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt 0}{\tt 1}^i{\tt 0}\,|\, i \mbox{ é ímpar}\}$.
        \item $\{w\in\{{\tt a},{\tt b},{\tt c}\}^*\,|\,w=w^R\}$.
       \end{list}}

       \emph{Solução:}

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $P \,\rightarrow\, {\tt 0} X {\tt 0}$ \\
              $X \,\rightarrow\, {\tt 1} X {\tt 1} \,|\, {\tt 1}$
        \item $P \,\rightarrow\, {\tt a} P {\tt a} \,|\, {\tt b} P {\tt b} \,|\, {\tt c} P {\tt c} \,|\,
                                 {\tt a}  \,|\, {\tt b} \,|\, {\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 $\{{\tt 0}{\tt 1}^i{\tt 0}\,|\, i \mbox{ é ímpar}\}$.
        \item O conjunto das palavras de $\{{\tt 0},{\tt 1}\}^*$ que cont\^em pelo menos um {\tt 00},
              mas nenhum {\tt 11}.
        \item $\{{\tt a},{\tt b}\}^*\{{\tt b},{\tt c}\}^*$.
       \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(2)(45,10){}
        \node(3)(65,10){}
        \node[Nmarks=r](4)(85,10){}

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

        \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](1)(25,25){}
        \node(2)(45,25){}
        \node[Nmarks=r](3)(65,25){}
        \node(4)(25,10){}
        \node[Nmarks=r](5)(65,10){}

        \drawedge[curvedepth=0](1,2){{\tt 0}}
        \drawedge[curvedepth=0, ELside=r](1,4){{\tt 1}}
        \drawedge[curvedepth=0](2,3){{\tt 0}}
        \drawedge[curvedepth=4](2,4){{\tt 1}}
        \drawloop[loopangle=0](3){{\tt 0}}
        \drawedge[curvedepth=4](3,5){{\tt 1}}
        \drawedge[curvedepth=4, ELside=r](4,2){{\tt 0}}
        \drawedge[curvedepth=4](5,3){{\tt 0}}
       \end{picture}
}
        \item  \ 
        
              \mbox{\setlength{\unitlength}{1mm}
       \begin{picture}(100,20)
        \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){}

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

 \item {\footnotesize Seja $\Sigma=\{{\tt}0,{\tt 1}\}$ e:
       \begin{itemize}
        \item $X=(\Sigma\Sigma)^*$
        \item $Y=\Sigma^*\{{\tt 11}\}\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-Y$.
       \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](p)(25,10){p}
        \node[Nmarks=r](i)(45,10){i}

        \drawedge[curvedepth=4](p,i){{\tt 0},{\tt 1}}
        \drawedge[curvedepth=4](i,p){{\tt 0},{\tt 1}}

        \node[Nmarks=i, iangle=180](1)(75,10){1}
        \node(2)(95,10){2}
        \node[Nmarks=r](3)(115,10){2}

        \drawloop[loopangle=90](1){{\tt 0}}
        \drawedge[curvedepth=4](1,2){{\tt 1}}
        \drawedge[curvedepth=4](2,1){{\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=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}

        \node[Nmarks=i, iangle=180](p1)(25,25){p1}
        \node(i2)(45,25){i2}
        \node(p3)(65,25){p3}
        \node(i1)(25,10){i1}
        \node(p2)(45,10){p2}
        \node(i3)(65,10){i3}

        \drawedge[curvedepth=4](p1,i2){{\tt 1}}
        \drawedge[curvedepth=4](p1,i1){{\tt 0}}
        \drawedge[curvedepth=4](i2,p1){{\tt 0}}
        \drawedge[curvedepth=0](i2,p3){{\tt 1}}
        \drawedge[curvedepth=4](p3,i3){{\tt 0},{\tt 1}}
        \drawedge[curvedepth=4](i1,p1){{\tt 0}}
        \drawedge[curvedepth=4](i1,p2){{\tt 1}}
        \drawedge[curvedepth=4](p2,i1){{\tt 0}}
        \drawedge[curvedepth=0](p2,i3){{\tt 1}}
        \drawedge[curvedepth=4](i3,p3){{\tt 0},{\tt 1}}
       \end{picture}
}

 \item Estados finais para reconhecer $X\cap Y$: $\{\mbox{p3}\}$. \\
       Estados finais para reconhecer $X-Y$: $\{\mbox{p1},\mbox{p2}\}$.
\end{list}
\end{enumerate}

\end{document}
