\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}/especial \hfill 30/10/2015 \\
 
\vspace*{2mm}
\noindent Cada questão vale 4 pontos.
\vspace*{2mm}
\begin{enumerate}
 \item Encontre uma expressão regular que denote a linguagem:
       $$\{w\in\{{\tt a},{\tt b},{\tt c}\}^*\,|\, w \mbox{ tem um único {\tt b} e
			 não termina com {\tt cc}}\}\mbox{.}$$

 \item Construa um AFD  reconheça $((aa+bb)^*cc)^*$.

% \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 $\{{\tt 0}^m{\tt 1}^{m+n}{\tt 0}^n \,|\, m+n\geq 2\}$.

 \item Descreva como seria possível, dada uma gramática regular $G$, determinar uma gramática
       regular $G'$ tal que $L(G)=L(G')$ e $G'$ não é ambígua.

 \item Construa uma gramática na forma normal de Chomsky equivalente à gramática:
       \begin{quote}
        $S \,\rightarrow\, AB \,|\, SCB$ \\
        $A \,\rightarrow\, {\tt a}A \,|\, C$ \\
        $B \,\rightarrow\, {\tt b}B \,|\, {\tt b}$ \\
        $C \,\rightarrow\, {\tt c}C \,|\, \lambda$
			 \end{quote}
       Deverão ser seguidos os passos recomendados em aula (os mesmos que são recomendados no
			 livro texto).

 \item Seja $L=\{{\tt a}^m{\tt b}^n{\tt c}^k\,|\,n,k\geq 0, m\not=n \mbox{ ou } n\not=k\}$. 
       Mostre que:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item $L$ é LLC.
        \item $\overline{L}$ não é LLC.
       \end{list}     
\end{enumerate}

\vspace{5mm}
\hrule \hrule

\begin{flushleft}
AFD: autômato finito determinístico. \\
GLC: gramática livre do contexto. \\
AP: autômato de pilha. \\
LLC: linguagem livre do contexto.
\end{flushleft}
\end{document}
 