\documentclass[12pt, a4paper]{report}

\usepackage[brazilian]{babel}
\usepackage[T1]{fontenc} 
\usepackage{fullpage}
\pagestyle{empty}
\newcounter{conta}
%\usepackage{gastex}
%\usepackage[usenames]{color}

\begin{document}

%\vspace*{1cm}
\noindent {\it Fundamentos da Teoria da Computação} \hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2014 \\
\noindent Professor: Newton José Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Segunda Prova} -- Turma N\hfill {15/4/2014}

\vspace*{1mm}
\noindent \textbf{Duração:} 1 hora e 30 minutos. \\
\noindent \textbf{Valor de cada questão:} a primeira questão vale 3 pontos e as restantes 5 pontos cada uma.

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

 \item Prove que $\{x{\tt c}^n\,|\, n\geq 0, x\in\{{\tt a},{\tt b},{\tt c}\}^* \mbox{ e } |x|=n\}$ não é uma
       linguagem regular.

 \item Encontre expressões regulares para as seguintes linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{w\in\{{\tt a},{\tt b}\}^*\,|\, |w|\leq 4\}$.
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, w \mbox{ contém número par de {\tt 0}s e ímpar de {\tt 1}s}\}$.
       \end{list}

 \item Construa gramáticas livres do contexto para as linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt a}^m{\tt b}^n\,|\,m<n\}$.
        \item $\{{\tt a}^m{\tt b}^n{\tt c}^k\,|\,k\geq m+n\}$.
       \end{list}

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

 \item Seja a gramática $H$:
	     \begin{enumerate}
	      \item[\ ] $P\,\rightarrow\, A$
	      \item[\ ] $A\,\rightarrow\,B,A \,|\, \lambda$
	      \item[\ ] $B\,\rightarrow\,( P )\,|\, {\tt a}$
	     \end{enumerate}
       Obtenha uma GLC equivalente a $H$ na forma normal de Chomsky. Siga os passos: (a) determine variáveis anuláveis;
			 (b) elimine regras $\lambda$; (c) obtenha conjuntos \textit{enc}; (d) elimine regras unitárias; (e) obtenha FNC.
\end{enumerate}

\end{document}
