\documentclass[12pt,a4paper]{report}

\usepackage[brazil]{babel}
\usepackage[latin1] {inputenc}

\usepackage{fullpage}
\usepackage{latexsym}
\usepackage{gastex}
\usepackage[usenames]{color}

\newcounter{conta}
\pagestyle{empty}
\begin{document}
 
\vspace*{11mm}
\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 2010 \\
\noindent Professor: Newton Jos\'{e} Vieira \\
\noindent {\bf Terceira Prova}  \hfill 23/12/2010

\vspace*{2mm}
Pesos das questões:
\begin{tabular}[t]{|r|c|c|c|c|c|}\hline
 \textit{questão:} & 1 & 2 & 3 & 4 & 5 \\ \hline
 \textit{peso:} & 4 & 4 & 3 & 3 & 4 \\ \hline
\end{tabular}

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

 \item O seguinte aut\^omato de pilha determin\'{\i}stico reconhece a linguagem dos par\^enteses
       balanceados:

       \mbox{\setlength{\unitlength}{1mm}
        \begin{picture}(120,20)
         \gasset{Nw=6, Nh=6, Nmr=3, loopdiam=6}

         \node[Nmarks=ir](1)(50,10){}
         \drawloop[loopangle=0](1){\shortstack{${\tt (}, \lambda/{\tt X}$ \\
                                               ${\tt )}, {\tt X}/\lambda$}}
        \end{picture}
       } \\

       Construa uma MT de duas fitas que reconhe\c{c}a tal linguagem simulando a pilha
       na segunda fita.

 \item Construa uma gram\'atica para a linguagem
       $\{{\tt a}^i{\tt b}^j{\tt c}^k\,|\,i<j<k\}$.
       Se a gram\'atica tiver menos de 10 regras voc\^e ganha 1 ponto extra.

 \item D\^e um exemplo de:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Uma linguagem recursivamente enumer\'avel n\~ao recursiva.
        \item Uma linguagem n\~ao recursivamente enumer\'avel.
       \end{list}

 \item Explique o que h\'a de errado com a seguinte argumenta\c c\~ao:
       \begin{quote}
        Dado um AP $M$, \'e poss\'{\i}vel construir uma GLC $G_M$
        tal que $G_M$ gera $L(M)$. Assim,  $L(M)=\Sigma^*$ se,
        e somente se, $L(G_M)=\Sigma^*$. Como o problema de determinar
        se $L(G)=\Sigma^*$, para GLCs $G$, \'e indecid\'{\i}vel, segue-se
        que o problema de determinar se $L(M)=\Sigma^*$, para APs $M$,
        \'e indecid\'{\i}vel.
       \end{quote}
       Corrija a argumenta\c c\~ao, mantendo a conclus\~ao da mesma.

 \item Mostre que \'e decid\'{\i}vel ou que n\~ao \'e:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Dada uma MT $M$, verificar se $L(M)$ é uma linguagem recursivamente enumerável.
        \item Dada uma MT $M$, verificar se $M$ escreve algum símbolo diferente de branco ($\sqcup$)
              em algum momento, quando a fita é iniciada em branco.
        \item Dada uma MT $M$, verificar se $M$ retorna ao estado inicial em algum momento
              para alguma entrada. 
        \item Dada uma MT $M$, determinar se $M$ reconhece alguma palavra com 10
              s\'{\i}mbolos.
       \end{list}
\end{enumerate}

\end{document}
