\documentclass[11pt,a4paper]{book}

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

\newcounter{conta}
\pagestyle{empty}

\begin{document}
 
\vspace*{15mm}
\noindent Pós-Graduação 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 2009 \\
\noindent Professor: Newton Jos\'{e} Vieira \\
\noindent {\bf Prova Suplementar} \hfill 16/12/2009

\vspace*{3mm}
\begin{flushleft}
Dura\c{c}\~ao: 1 hora e 30 minutos.
\end{flushleft}

\begin{flushleft}
Escolha \textbf{5 quest\~oes}. Cada uma vale \textbf{6 pontos} (3 pontos extra).
\end{flushleft}

\begin{enumerate}
 \item Construa um AFD que reconhe\c{c}a a linguagem $(a+b+c)^*a(a+b)(a+b+c)$.

 \item Construa uma ER que denote a linguagem reconhecida pelo AFD:

       \begin{picture}(120,20)
        \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}

        \node[Nmarks=i, iangle=180](1)(40,7){1}
        \node[Nmarks=r](2)(60,7){2}
        \node[Nmarks=r](3)(80,7){3}

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

 \item Fa\c{c}a uma GLC que gere as express\~oes regulares sobre o alfabeto $\{{\tt 0},{\tt 1}\}$. Pode ser no estilo ``para cada operador, um par de par\^enteses'' (como no livro-texto e visto em aula). Inclua apenas os tr\^es operadores cl\'assicos. Se sua gram\'atica for amb\'{\i}gua, mostre que \'e.

 \item Prove que $\{{\tt a}^{n^2+1}\,|\, n\geq 0\}$ n\~ao \'e linguagem livre do contexto.

 \item Seja um modelo de MT an\'alogo ao da MT-padr\~ao, com a diferen\c{c}a de que existem dois estados especiais:
       um de \emph{aceita\c{c}\~ao}, $a$, e outro de \emph{rejei\c{c}\~ao}, $r$. Nesse modelo, a MT aceita uma
       palavra somente se atinge o estado $a$ ao processar a palavra; e a MT rejeita uma palavra somente se
       atinge o estado $r$ ao processar a palavra. Que classe de linguagens tal tipo de MT pode reconhecer? Justifique.

 \item Seja o seguinte PD: dadas duas MTs $M_1$ e $M_2$ que \underline{entrem em \emph{loop\/} ao processar $\lambda$},
       determinar se existe um n\'umero natural $n$ tal que a dist\^ancia (n\'umero de c\'elulas) m\'axima
       entre os cabe\c{c}otes de $M_1$ e $M_2$ \'e $n$ quando $M_1$ e $M_2$ processarem $\lambda$
       \emph{em paralelo} (ou seja, quando ambas efetuarem a $n$-\'esima transi\c{c}\~ao ao mesmo tempo para
       todo $n\geq 1$); veja figura abaixo. Mostre que tal PD \'e indecid\'{\i}vel.

       \begin{picture}(120,30)
        \put(18,22.5){\makebox(0,0)[r]{$M_1$:}}
        \put(37.5,15){\vector(0,1){4}}
        \put(20,20){\line(1,0){80}}
        \put(20,20){\line(0,1){5}}
        \put(20,25){\line(1,0){80}}
        \put(22.5,22.5){\makebox(0,0){$<$}}
        \put(25,20){\line(0,1){5}}
        \put(30,20){\line(0,1){5}}
        \put(35,20){\line(0,1){5}}
        \put(40,20){\line(0,1){5}}
        \put(45,20){\line(0,1){5}}
        \put(50,20){\line(0,1){5}}
        \put(55,20){\line(0,1){5}}
        \put(60,20){\line(0,1){5}}
        \put(65,20){\line(0,1){5}}
        \put(70,20){\line(0,1){5}}
        \put(75,20){\line(0,1){5}}
        \put(80,20){\line(0,1){5}}
        \put(85,20){\line(0,1){5}}
        \put(90,20){\line(0,1){5}}
        \put(95,22.5){\makebox(0,0){$\cdots$}}

        \put(85,15){\makebox(0,0)[l]{dist\^ancia atual: 8}}

        \put(18,7.5){\makebox(0,0)[r]{$M_2$:}}
        \put(77.5,0){\vector(0,1){4}}
        \put(20,5){\line(1,0){80}}
        \put(20,5){\line(0,1){5}}
        \put(20,10){\line(1,0){80}}
        \put(22.5,7.5){\makebox(0,0){$<$}}
        \put(25,5){\line(0,1){5}}
        \put(30,5){\line(0,1){5}}
        \put(35,5){\line(0,1){5}}
        \put(40,5){\line(0,1){5}}
        \put(45,5){\line(0,1){5}}
        \put(50,5){\line(0,1){5}}
        \put(55,5){\line(0,1){5}}
        \put(60,5){\line(0,1){5}}
        \put(65,5){\line(0,1){5}}
        \put(70,5){\line(0,1){5}}
        \put(75,5){\line(0,1){5}}
        \put(80,5){\line(0,1){5}}
        \put(85,5){\line(0,1){5}}
        \put(90,5){\line(0,1){5}}
        \put(95,7.5){\makebox(0,0){$\cdots$}}
       \end{picture}

       (O conte\'udo das fitas n\~ao \'e mostrado por ser irrelevante.)
\end{enumerate}

\end{document}