\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\c{c}\~ao}
\hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2013 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Segunda Prova} -- Turma W\hfill {09/5/2013}

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

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

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

 \item Encontre express\~oes regulares para as seguintes linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{w\in\{{\tt a},{\tt b},{\tt c}\}^*\,|\,$ o n\'umero de {\tt a}s
               mais o de {\tt b}s em $w$ \'e par$\}$.
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, w$ cont\'em o s\'{\i}mbolo
              \verb+1+ e $\eta(w) \mbox{ mod } 3=0\}$.  ($\eta(w)$ é o número representado por $w$ na base 2.)
       \end{list}

 \item Construa gramáticas livres do contexto para as linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt 0}^{2n}{\tt 1}^{3n}\,|\, n\geq 0\}$.
        \item $\{{\tt 0}^n{\tt 1}^n\,|\,n\geq 1\}^2\{w\in\{{\tt 0},{\tt 1}\}^*\,|\,w=w^R\}
              \{{\tt 0}^n{\tt 1}^n\,|\,n\geq 1\}^2$.
       \end{list}

 \item Seja a gram\'atica:
       \begin{quote}
        $G$: $X \,\rightarrow\, {\tt a}X{\tt b} \,|\, X{\tt b} \,|\, \lambda$
       \end{quote}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Mostre que $G$ é amb\'{\i}gua.
        \item Construa uma gram\'atica n\~ao amb\'{\i}gua equivalente $G$.
       \end{list}

 \item Seja a gram\'atica:
	     \begin{enumerate}
	      \item[\ ] $P\,\rightarrow\, ABC$
	      \item[\ ] $A\,\rightarrow\,{\tt a} A {\tt b} \,|\, \lambda$
	      \item[\ ] $B\,\rightarrow\,{\tt b} B \,|\, {\tt b}$
	      \item[\ ] $C\,\rightarrow\, {\tt b} C {\tt c} \,|\, \lambda$
	     \end{enumerate}
       Obtenha uma GLC equivalente na forma normal de Chomsky. Deixe bem claros todos os passos executados,
			 assim como a ordem em que foram executados, para chegar à gramática final.
\end{enumerate}

\end{document}
