\documentclass[11pt, a4paper]{report}

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

\usepackage{fullpage}
\pagestyle{empty}
\newcounter{conta}
\usepackage{gastex}
\usepackage[usenames]{color}

\begin{document}

\vspace*{1cm}
\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2010 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Quarta Prova} -- Turma W \hfill {08/07/2010}

\vspace*{1mm}
\noindent \textbf{Dura\c{c}\~ao:} 1 hora e 30 minutos. \\
\noindent \textbf{Valor de cada quest\~ao:} 4 pontos cada uma, exceto a última, que vale 3 pontos.

\vspace*{2mm}
\begin{enumerate}
 \item Seja o seguinte diagrama de estados de uma MT n\~ao determin\'{\i}stica com alfabeto
       de entrada $\{{\tt a},{\tt b},{\tt c}\}$:
       \begin{center} \small
       \begin{picture}(110,40)
        \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}
        \node[Nmarks=i](1)(20,20){1}
        \node(2)(40,30){2}
        \node(3)(65,30){3}
        \node(4)(40,10){4}
        \node(5)(65,10){5}
        \node[Nmarks=r](6)(85,20){6}

        \drawloop[loopangle=120](1){\shortstack{${\tt b}/{\tt b}\;{\tt D}$ \\ ${\tt c}/{\tt c}\;{\tt D}$}}
        \drawedge[curvedepth=0](1,2){${\tt a}/{\tt b}\;{\tt D}$}
        \drawedge[curvedepth=0, ELside=r](1,4){${\tt a}/{\tt c}\;{\tt D}$}
        \drawloop[loopangle=90](2){${\tt b}/{\tt b}\;{\tt D}$}
        \drawedge[curvedepth=0](2,3){$\sqcup/\sqcup\;{\tt E}$}
        \drawloop[loopangle=90](3){${\tt b}/{\tt b}\;{\tt E}$}
        \drawedge[curvedepth=0](3,6){$\langle/\langle\;{\tt D}$}
        \drawloop[loopangle=270](4){${\tt c}/{\tt c}\;{\tt D}$}
        \drawedge[curvedepth=0, ELside=r](4,5){$\sqcup/\sqcup\;{\tt E}$}
        \drawloop[loopangle=270](5){${\tt c}/{\tt c}\;{\tt E}$}
        \drawedge[curvedepth=0, ELside=r](5,6){$\langle/\langle\;{\tt D}$}
       \end{picture}
       \end{center}
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item Que linguagem ela reconhece?
        \item Construa uma MT equivalente determin\'{\i}stica.
       \end{list}

 \item Seja a linguagem de listas, Li, cuja sintaxe pode ser descrita
       pela gram\'atica $(\{L,S,X\},\{{\tt a},(,)\},R,L)$, sendo $R$ constitu\'{\i}do das regras:
       \begin{enumerate}
        \item[\ ] $L\,\rightarrow\,(S)$
        \item[\ ] $S\,\rightarrow\, XS \,|\, \lambda$
        \item[\ ] $X\,\rightarrow\, {\tt a} \,|\, L$
       \end{enumerate}
       Exemplos de listas: $()$, $({\tt a})$, $(())$, $({\tt a}\,())$, $(({\tt a})\,{\tt a})$,
       $({\tt a}\,()\,(({\tt a}\,{\tt a})\,{\tt a}\, {\tt a}))$ etc.

       Construa o diagrama de estados de uma MT de duas fitas que reconhe\c ca $L(\mbox{Li})$.

 \item Construa uma gram\'atica irrestrita que gere $\{{\tt a}^{n}{\tt b}^n{\tt c}^{k}\,|\,k>n\}$.
       Caso a gram\'atica seja sens\'{\i}vel ao contexto, voc\^e ganha mais um ponto.


 \item Responda sim ou n\~ao. Para cada resposta certa voc\^e ganha meio ponto
       e para cada resposta errada perde meio ponto:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item Qualquer linguagem sens\'{\i}vel ao contexto \'e recursivamente enumer\'avel.
        \item O complemento de uma linguagem recursiva pode n\~ao ser recursiva.
        \item Se $L$ \'e recursivamente enumer\'avel, mas n\~ao recursiva, n\~ao existe m\'aquina de Turing
              que reconhe\c{c}a $\overline{L}$.
        \item Gram\'aticas irrestritas s\'o geram linguagens recursivas.
        \item Se $L$ n\~ao \'e recursiva, $\overline{L}$ tamb\'em n\~ao \'e.
        \item Gram\'aticas irrestritas geram linguagens recursivamente enumer\'aveis.
       \end{list}
\end{enumerate}

\end{document}
 
