\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 2015 \\
\noindent Professor: Newton José Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\it Segunda Prova} --- Turma N \hfill 19/5/2015

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

%\vspace*{2mm}
\begin{enumerate}
 \item Prove que os seguintes conjuntos não são linguagens regulares:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt a}^n{\tt b}^k\,|\, n>k\}$ \\ $\!\!\Rightarrow$\ use o lema do bombeamento.
        \item $\{w\in\{{\tt a},{\tt b}\}^*\,|\, w \mbox{ tem mais {\tt a}s que {\tt b}s}\}\{{\tt c}\}^*$ \\
				      $\Rightarrow$\ use o resultado anterior e propriedades de fechamento.
       \end{list}

 \item Obtenha ERs que denotem as linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, w \mbox{ tem um número par de {\tt 0}s antes de seu primeiro {\tt 1}}\}\cup\{{\tt 0}\}^*$.
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, w \mbox{ não contém a subpalavra {\tt 010}}\}$.
       \end{list}

 \item Construa um APD com reconhecimento padrão (estado final \underline{e} pilha vazia) que reconheça a linguagem
       $\{{\tt a}^n{\tt b}^k\,|\, n>k\}\{{\tt c}\}^+$, caso seja possível. Se não for possível, faça um APN.

 \item Construa GLCs para as linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{w\in \{{\tt 0},{\tt 1},\#\}^*\,|\,w \mbox{ não contém {\tt 00}, {\tt 01}, {\tt 10}, nem {\tt 11}}\}$.
        \item $\{{\tt a}^m{\tt b}^n{\tt c}^k\,|\,k>m+n\}$.
       \end{list}

 \item Seja a gramática $G$ de regras $X \,\rightarrow\, XX \,|\, {\tt 0} \,|\, {\tt 1}$.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Mostre que $G$ é ambígua.
        \item Construa uma gramática não ambígua equivalente a $G$.
       \end{list}

 \item Transforme a GLC a seguir em uma equivalente na forma normal de Chomsky.
	     \begin{enumerate}
	      \item[\ ] $F\,\rightarrow\, FTC  \,|\, CD$
	      \item[\ ] $T\,\rightarrow\, TC \,|\, \lambda$
	      \item[\ ] $C\,\rightarrow\, CD \,|\, D$
	      \item[\ ] $D\,\rightarrow\, {\tt a}D{\tt b} \,|\, \lambda$
	     \end{enumerate}
			Explicite os passos necessários para a transformação, como visto nas aulas.
\end{enumerate}
\end{document}