\documentclass[12pt,a4paper]{report}

\usepackage[brazil]{babel}
\usepackage[latin1] {inputenc}
\usepackage{fullpage}


\newcounter{conta}
\newcounter{conta2}
\begin{document}
 
\noindent Pós-Graduação em Ciência da Computação  \hfill DCC/ICEx/UFMG \\
{\it Teoria de Linguagens}  \hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2015 \\
\textbf{Segunda Prova} \hfill 27/10/2015 \\
 
\vspace*{2mm}
\noindent Cada questão vale 4 pontos.
\vspace*{2mm}
\begin{enumerate}
 \item Encontre uma expressão regular que denote $\{{\tt 0}^m{\tt 1}^n\,|\, m+n \mbox{ é ímpar }\}$.

 \item Construa um AFN  de 3 estados que reconheça $(a+b)^*bc^*+(a+d)^*dc^*$.

% \item Construa uma expressão regular que denote a linguagem reconhecida por:

%         \begin{picture}(50,42)
%          \gasset{Nw=6, Nh=6, Nmr=4, ELdist=0.5, loopdiam=5, fillgray=0.9}

%          \node[Nmarks=i](1)(20,32){1}
%          \node(2)(40,32){2}
%          \node[Nmarks=ir](4)(20,12){4}
%          \node[Nmarks=r](3)(40,12){3}

%          \drawloop[loopangle=90](1){\tt a}
%          \drawedge[curvedepth=3](1,2){\tt a}
%          \drawedge[curvedepth=3](2,1){\tt b}
%          \drawloop[loopangle=0](2){\tt b}
%          \drawedge[curvedepth=3](2,3){\tt c}
%          \drawloop[loopangle=0](3){\tt c}
%          \drawedge[curvedepth=3](3,2){\tt b}
%          \drawedge[curvedepth=3](3,4){\tt a}
%          \drawedge[curvedepth=3](4,3){\tt b}
%          \drawedge[curvedepth=0](4,1){$\lambda$}
%         \end{picture}

 \item Construa uma GLC e um AP para a linguagem $\{\verb+a+^{m+n}\verb+b+^{m}\verb+c+^n \,|\, m+n\geq 1\}$.

 \item Descreva como eliminar regras unitárias em GLCs.

 \item Use o lema do bombeamento para mostrar que $\{\verb+0+^{n^2} \,|\, n\geq 0\}$ não é LLC.

 \item Prove que a afirmativa
       \begin{quote}
        \emph{se $L$ não é uma LLC, então $(L-X)\cup(X-L)$ não é uma LLC}
			 \end{quote}
			 é ou não verdadeira, considerando os casos em que:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $X$ é finita.
        \item $X$ é regular.
       \end{list}
\end{enumerate}

\vspace{5mm}
\hrule \hrule

\begin{flushleft}
AFN: autômato finito não determinístico \underline{sem transições $\lambda$}. \\
GLC: gramática livre do contexto. \\
AP: autômato de pilha. \\
LLC: linguagem livre do contexto.
\end{flushleft}
\end{document}
