\documentclass[12pt, a4paper]{report}

\usepackage[brazilian]{babel}
\usepackage[T1]{fontenc} 
\usepackage{amsfonts}

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

\newcounter{conta}
\pagestyle{empty}

\begin{document}

\noindent {\it Fundamentos da Teoria da Computação} \hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2016 \\
\noindent Professor: Newton José Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\it Terceira Prova}  \hfill 28/6/2016

\vspace*{3mm}
\noindent \textbf{Cada questão vale 4 pontos.}

\begin{enumerate}
 \item Dê exemplos de linguagens $L_1$ e $L_2$ tais que $L_1\subseteq L_2$ e:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $L_1$ é LLC e $L_2$ também é LLC.
        \item $L_1$ é LLC, mas $L_2$ não é LLC.
        \item $L_1$ não é LLC, mas $L_2$ é LLC.
        \item $L_1$ não é LLC e $L_2$ também não é LLC.
       \end{list}

 \item Crie MTs que reconheçam $(aa)^*$:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item por parada;
        \item por estado final.
       \end{list}

 \item Faça uma MT de \emph{duas fitas} que reconheça a linguagem:
       $$\{xx^Ry \,|\, x\in\{{\tt 0},{\tt 1}\}^*, y\in\{{\tt 0},{\tt 1}\}^* \mbox{ e } |x|>|y|\}\mbox{.}$$
			 Ela pode ser \emph{não determinística} (muito mais simples\ldots).

 \item Construa uma gramática sensível ao contexto que gere $$\{xwx \,|\, x\in\{{\tt 0},{\tt 1}\}^* \mbox{ e }
       w\in\{{\tt a},{\tt b}\}^+\}\mbox{.}$$

 \item Mostre que se o problema da parada fosse decidível, então \mbox{toda LRE seria recursiva}.

 \item Mostre que é decidível ou que não é:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item dada uma gramática irrestrita $G$, determinar se $L(G)\not=\emptyset$.
        \item dada uma MT $M$, determinar se $M$ passa duas vezes por algum estado ao processar $\lambda$.
			 \end{list}
\end{enumerate}

\vspace*{3mm}
\hrule
\vspace*{.5mm}
\hrule

\vspace*{3mm}
\begin{flushleft}
 LLC: linguagem livre do contexto; \\
 LRE: linguagem recursivamente enumerável; \\
 MT: máquina de Turing;
\end{flushleft}

\end{document}
