\documentclass[11pt,a4paper]{book}

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

\newcounter{conta}
\pagestyle{empty}

\begin{document}
 
\vspace*{15mm}
\noindent P\'os-Gradua\c{c}\~ao em Ci\^{e}ncia da Computa\c{c}\~{a}o
 \hfill DCC/ICEx/UFMG \\
\noindent {\it Teoria de Linguagens}
 \hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2008 \\
\noindent Professor: Newton Jos\'{e} Vieira \\
\noindent {\bf Segunda Prova} \hfill 22/10/2008

\vspace*{3mm}
\begin{flushleft}
Valor de cada quest\~ao: 4,5 pontos (item a: 2,5 pontos, item b: 2 pontos).
\end{flushleft}

\begin{enumerate}
 \item Seja $M$ o aut\^omato finito com o seguinte diagrama de estados:
       \begin{center}
        \mbox{\setlength{\unitlength}{1mm}
         \begin{picture}(140,20)
          \gasset{Nw=6, Nh=6, Nmr=3, loopdiam=6}

          \node[Nmarks=ir](1)(20,10){1}
          \node[Nmarks=r](2)(40,10){2}
          \node[Nmarks=r](3)(60,10){3}
          \node[Nmarks=r](4)(80,10){4}

          \drawloop[loopangle=90](1){{\tt 1}}
          \drawedge[curvedepth=2](1,2){{\tt 0}}
          \drawedge[curvedepth=2](2,1){{\tt 1}}
          \drawedge[curvedepth=0](2,3){{\tt 0}}
          \drawedge[curvedepth=0](3,4){{\tt 0},{\tt 1}}
         \end{picture}
        }
       \end{center}
      Obtenha express\~oes regulares que denotem as linguages:
      \begin{list}{\alph{conta})}{\usecounter{conta}}
       \item $L(M)$;
       \item $\overline{L(M)}$. 
      \end{list} 
 
 \item Para cada linguagem a seguir, construa um APD, se poss\'{\i}vel. Se n\~ao for poss\'{\i}vel,
       construa um APN. Crit\'erio de reconhecimento: por estado final {\bf e} pilha vazia.
       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, w \mbox{ tem algum prefixo com mais {\tt0}s que {\tt 1}s}\}$;
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, w \mbox{ tem mais {\tt0}s que {\tt 1}s}\}$. 
       \end{list}
       
 \item Fa\c{c}a gram\'aticas livres do contexto que reconhe\c{c}am:
       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt a}^m{\tt b}^n{\tt c}^k\,|\,n\geq m \mbox{ ou } n\geq k\}$.
        \item $\{{\tt a}^m{\tt b}^n{\tt c}^k\,|\,m+n\geq k\}$.
       \end{list}

 \item Seja a gram\'atica $G$:
       \begin{tabbing}
        xxx\= \kill
           \> $P\rightarrow AB$ \\
           \> $A\rightarrow {\tt a}A{\tt b} \,|\, \lambda$ \\
           \> $B\rightarrow {\tt b}B{\tt a} \,|\, \lambda$
       \end{tabbing}
       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item Obtenha uma gram\'atica equivalente a $G$ na forma normal de Greibach.
        \item A partir de $G$, obtenha um APN que reconhe\c{c}a $L(G)$ usando um dos m\'etodos
              vistos em aula.
       \end{list}     
\end{enumerate}

\end{document}