\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 \textbf{Segunda Prova}  \hfill 19/5/2016

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

%\vspace*{2mm}
\begin{enumerate}
% \item Prove que $\{x{\tt b}y\,|\, x,y\in \{{\tt a},{\tt b}\}^* \mbox{ e } |x|=|y|\}$ é regular ou que não é regular.
 \item Sejam $L_1=\{{\tt 0}^n \,|\, n\geq 1000\}$ (regular), e $L_2=\{{\tt 0}^n \,|\, n \mbox{ é número primo}\}$
       (não regular). Para cada linguagem a seguir, mostre que ela é regular ou que não é:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $L_2-L_1$;
        \item $L_1\cap L_2$.
       \end{list}
 \item Obtenha expressões regulares que denotem as linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, w \mbox{ inicia com {\tt 0} e } |w| \mbox{ é par}\}$.
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, |w|>0 \mbox{ e } w \mbox{ tem um único {\tt 0} nas posições ímpares}\}$.
				      Exemplos, sublinhando o zero na posição ímpar: \underline{\tt 0}, \underline{\tt 0}{\tt 0},
							\underline{\tt 0}{\tt 1}, \underline{\tt 0}{\tt 01}, \underline{\tt 0}{\tt 11}, {\tt 10}\underline{\tt 0},
							{\tt 11}\underline{\tt 0}, \underline{\tt 0}{\tt 010} etc.
       \end{list}

 \item Construa:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Um APD que reconheça $\{{\tt a}^n({\tt cba})^n\,|\, n\in\mathbb{N}\}$.
				\item Um APN que reconheça $\{{\tt a}^n({\tt abc})^n\,|\, n\in\mathbb{N}\}$.
        \end{list}

 \item Construa GLCs para as linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{x{\tt b}y\,|\, x,y\in \{{\tt a},{\tt b}\}^* \mbox{ e } |x|=|y|\}$.
        \item $\{{\tt a}^m{\tt b}^k{\tt c}^n\,|\,k>m+n\}$.
       \end{list}

 \item Mostre que a gramática a seguir é ambígua:
       \begin{quote}
        $A\,\rightarrow\, {\tt 0}A{\tt 1} \,|\, B$ \\
        $B\,\rightarrow\, {\tt 0}B{\tt 11} \,|\, C$ \\
        $C\,\rightarrow\, {\tt 0}C{\tt 111} \,|\, \lambda$
       \end{quote}

 \item Transforme a GLC a seguir em uma equivalente na forma normal de Chomsky.
	     \begin{enumerate}
	      \item[\ ] $P\,\rightarrow\, {\tt a}P{\tt b}  \,|\, A$
	      \item[\ ] $A\,\rightarrow\, B{\tt a}B \,|\, {\tt a}B$
	      \item[\ ] $B\,\rightarrow\, {\tt a}B{\tt c} \,|\, \lambda$
	     \end{enumerate}
			 Primeiro elimine regras $\lambda$, depois unitárias, etc., como preconiza o método visto.
\end{enumerate}

\vspace*{2mm}
\hrule

\vspace*{2mm}
\noindent Abreviaturas:
\begin{flushleft}
 APD: autômato de pilha determinístico. \\
 APN: autômato de pilha não determinístico. \\
 GLC: gramática livre do contexto.
\end{flushleft}

\end{document}