\documentclass[11pt, a4paper]{report}

\usepackage[brazil]{babel}
\usepackage[latin1]{inputenc}
\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 2012 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Primeira Prova/Turma W}/Solução do professor \hfill {\bf 03/04/2012}

\vspace*{3mm}
\noindent Os ítens das questões valem 1,5 pontos cada um, exceto o item (c) da questão 4, que vale 2.

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

 \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{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 em que todo {\tt 0} \'e seguido de {\tt 1}.
        \item O conjunto das palavras em que começam com {\tt 00} ou {\tt 11} e terminam com {\tt 01} ou {\tt 10}.
       \end{list}}

       \textit{Solução}:

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt 01},{\tt 1}\}^*$
        \item $\{{\tt 00},{\tt 11}\}\{{\tt 0},{\tt 1}\}^*\{{\tt 01},{\tt 10}\}\cup\{{\tt 001},{\tt 110}\}$.
       \end{list}

 \item {\footnotesize Identifique as linguagens que s\~ao geradas pelas gram\'aticas a seguir:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $G_0=(\{A,B\},\{{\tt 0},{\tt 1}\},R_0,A)$.
              \begin{enumerate}
               \item[$R_0$:]  $A\,\rightarrow\,{\tt 0} A {\tt 0} \,|\, B {\tt 1} $
               \item[\ ]      $B\,\rightarrow\, {\tt 1} B {\tt 1} \,|\, \lambda$
              \end{enumerate}
        \item $G_1=(\{P,X\},\{{\tt 0},{\tt 1}\},R_1,P)$.
              \begin{enumerate}
               \item[$R_1$:]  $P\,\rightarrow\,{\tt 0} X {\tt 0} X {\tt 10}$
               \item[\ ]      $X\,\rightarrow\,{\tt 11} X \,|\, \lambda$
              \end{enumerate}
       \end{list}}

       \textit{Solução}:

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt 0}^n{\tt 1}^{2k+1}{\tt 0}^n\,|\,n,k\geq 0\}$
        \item $\{{\tt 0}\}\{{\tt 11}\}^*\{{\tt 0}\}\{{\tt 11}\}^*\{{\tt 10}\}$ 
       \end{list}

 \item {\footnotesize Obtenha gramáticas que gerem:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item O conjunto das palavras com número par de {\tt 0}s.
        \item O conjunto das palavras em que começam com {\tt 00} ou {\tt 11} e terminam com {\tt 01} ou {\tt 10}.
        \item $\{{\tt 0}^m{\tt 1}^n\,|\, m < n\}$.
       \end{list}}

       \textit{Solução}:

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $G_a=(\{A\},\{{\tt 0},{\tt 1}\},R_a,A)$.
              \begin{enumerate}
               \item[$R_a$:]  $A\,\rightarrow\,{\tt 1} A \,|\, {\tt 0}A{\tt 0}A \,|\, \lambda$
              \end{enumerate}
        \item $G_b=(\{A,B\},\{{\tt 0},{\tt 1}\},R_b,A)$.
              \begin{enumerate}
               \item[$R_b$:]  $A\,\rightarrow\,{\tt 00} B \,|\, {\tt 11}B \,|\, {\tt 001} \,|\, {\tt 110}$
               \item[\ ]      $B\,\rightarrow\, {\tt 0} B \,|\, {\tt 1}B \,|\, {\tt 01} \,|\, {\tt 10}$
              \end{enumerate}
        \item $G_c=(\{A\},\{{\tt 0},{\tt 1}\},R_c,A)$.
              \begin{enumerate}
               \item[$R_c$:]  $A\,\rightarrow\,{\tt 0} A {\tt 1}\,|\, A{\tt 1} \,|\, {\tt 1}$
              \end{enumerate}
       \end{list}
\pagebreak
 \item {\footnotesize Sejam
       \begin{itemize}
        \item $L_1=\{{\tt 0},{\tt 1}\}^*\{{\tt 1}\}\{{\tt 0},{\tt 1}\}^*$;
        \item $L_2=\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, w \mbox{ não contém }{\tt 00}\}$.
       \end{itemize}
       Construa autômatos finitos determinísticos que reconheçam:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $L_1$.
        \item $L_2$.
        \item $L_1-L_2$. Para isto, faça o produto dos autômatos que reconhecem $L_1$ e $\overline{L_2}$
              (já que $L_1-L_2=L_1\cap\overline{L_2}$).
       \end{list}}

       \textit{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](A)(25,10){A}
                \node[Nmarks=r](B)(45,10){B}

                \drawedge[curvedepth=0](A,B){{\tt 1}}
                \drawloop[loopangle=90](A){{\tt 0}}
                \drawloop[loopangle=90](B){{\tt 0},{\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){1}
                \node[Nmarks=r](2)(45,10){2}
                \node(3)(65,10){3}

                \drawedge[curvedepth=4](1,2){{\tt 0}}
                \drawloop[loopangle=90](1){{\tt 1}}
                \drawedge[curvedepth=4](2,1){{\tt 1}}
                \drawedge[curvedepth=0](2,3){{\tt 0}}
                \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)(25,25){A1}
                \node(B1)(25,10){B1}
                \node(A2)(45,25){A2}
                \node(B2)(45,10){B2}
                \node(A3)(65,25){A3}
                \node[Nmarks=r](B3)(65,10){B3}

                \drawedge[curvedepth=0](A1,A2){{\tt 0}}
                \drawedge[curvedepth=0](A1,B1){{\tt 1}}
                \drawedge[curvedepth=0](A2,A3){{\tt 0}}
                \drawedge[curvedepth=-1,ELside=r](A2,B1){{\tt 1}}
                \drawloop[loopangle=270](B1){{\tt 1}}
                \drawedge[curvedepth=3](B1,B2){{\tt 0}}
                \drawedge[curvedepth=0](B2,B3){{\tt 0}}
                \drawedge[curvedepth=3](B2,B1){{\tt 1}}
                \drawloop[loopangle=270](B3){{\tt 0},{\tt 1}}
                \drawedge[curvedepth=0](A3,B3){{\tt 1}}
                \drawloop[loopangle=90](A3){{\tt 0}}
               \end{picture}
              }

       \end{list}

\end{enumerate}

\end{document}
