\documentclass[12pt,a4paper]{report}

\usepackage[brazilian]{babel}
\usepackage[T1]{fontenc} 

\usepackage{fullpage}
\usepackage{latexsym}
\usepackage{gastex}
\usepackage[usenames]{color}

\usepackage{comment}

\newcounter{conta}
\pagestyle{empty}
\begin{document}
 
\noindent Pós-Graduação em Ciência da Computação \hfill DCC/ICEx/UFMG \\
\noindent {\it Teoria de Linguagens} \hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2017 \\
\noindent Professor: Newton José Vieira \\
\noindent {\it Prova Suplementar}

\vspace*{3mm}
\begin{enumerate}
 \item Apresente diagramas de estados de AFDs mínimos que reconheçam:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}
        \item $(00+1)^*(0+11)^*$;
        \item o complemento da linguagem anterior.
       \end{list}
 \item Seja o AFN$\lambda$ com o diagrama de estados:

       \begin{picture}(65,40)
        \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}
        \node[Nmarks=i, iangle=180](1)(10,20){1}
        \node(2)(25,30){2}
        \node(3)(25,10){3}
        \node[Nmarks=r](4)(40,20){4}

%        \put(30,0){\makebox(0,0){\textbf{(a) AFN$\lambda$ 1.}}}
        \drawedge[curvedepth=0](1,2){$\lambda$}
        \drawedge[curvedepth=0, ELside=r](1,3){{\tt a}}
        \drawedge[curvedepth=0](2,4){{\tt b}}
        \drawloop[loopangle=90](2){{\tt a}}
        \drawedge[curvedepth=0, ELside=r](3,4){$\lambda$}
        \drawloop[loopangle=270](3){{\tt b}}
        \drawloop[loopangle=0](4){{\tt c}}
       \end{picture}

       Obtenha:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}
        \item um AFN equivalente usando o método visto no curso;
        \item para cada $(e,s)$ tal que $s\not=\lambda$ e $|\delta(e,s)|>1$ indique o cálculo de
				      $\delta'(e,s)$, sendo $\delta$ a função de transição do AFN$\lambda$ e $\delta'$ a do
							AFN obtido.
       \end{list}
  \item Para a linguagem $\{x\overline{x}^R\,|\, x\in \{{\tt 0},{\tt 1}\}^+\}$ ($\overline{x}$ é o complemento de $x$):
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}
        \item mostre que ela é livre do contexto;
        \item prove que ela não é regular usando o teorema da invariância à direita ou o lema do bombeamento.
			 \end{list}

 \item Seja a gramática:
	     \begin{enumerate}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}
	      \item[\ ] $A\,\rightarrow\, ABC \,|\, A{\tt a}$
	      \item[\ ] $B\,\rightarrow\, CBC \,|\, CE$
	      \item[\ ] $C\,\rightarrow\, EB \,|\, {\tt b}C \,|\, \lambda$
	      \item[\ ] $D\,\rightarrow\, BB \,|\, AE \,|\, {\tt b}$
	      \item[\ ] $E\,\rightarrow\, DCC \,|\, {\tt ab} \,|\, \lambda$
	      \end{enumerate}
       Explicite o conjunto de variáveis anuláveis e apresente uma GLC equivalente sem regras $\lambda$.

 \item Seja $L$ uma linguagem \emph{não} recursiva. Mostre que:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}
        \item $\overline{L}$ não é recursiva;
        \item se $L$ é LRE, então $\overline{L}$ não é LRE.
       \end{list}

\item Para cada problema a seguir, mostre que ele é decidível ou que não é:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}
			  \item dada uma MT $M$, determinar se $R\langle M\rangle \in L(M)$;
			  \item dadas MTs $M_1$ e $M_2$, determinar se $\lambda\in L(M_1)\cup L(M_2)$;
			  \item dada uma MT $M$, determinar se $|L(M)| \leq 1$;
			  \item dada uma MT $M$, determinar se ela é a única que reconhece $L(M)$.
       \end{list}
\end{enumerate}

\end{document}
