\documentclass[11pt]{report}

\usepackage[brazil]{babel}
\usepackage[latin1] {inputenc}
\usepackage{fullpage}
\pagestyle{empty}
\usepackage{gastex}
\usepackage[usenames]{color}

\newcounter{conta}
\pagestyle{empty}

\begin{document}

\vspace*{1cm}
\noindent Departamento de Ciência da Computação \hfill ICEx/UFMG \\
\noindent {\it Teoria de Linguagens} \hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2018 \\
\noindent Professor: Newton José Vieira \\
\noindent {\bf Primeira Prova} \hfill 18/9/2018 \hfill Valor: 24 pontos

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

 \item Descreva, em português, as seguintes linguagens sobre o alfabeto $\{{\tt 0},{\tt 1}\}$:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}}
			  \item $\{{\tt 0},{\tt 1}\}^*\{{\tt 1}\}\{{\tt 0},{\tt 1}\}$;
			  \item $\{{\tt 0}\}\{{\tt 0},{\tt 1}\}^*\cup\{{\tt 0},{\tt 1}\}^*\{{\tt 1}\}$;
			  \item $\{{\tt 01},{\tt 1}\}^*$;
			  \item $\{{\tt 0}\}^*\{{\tt 1}\}(\{{\tt 0}\}\cup\{{\tt 1}\}\{{\tt 0}\}^*\{{\tt 1}\})^*$.
       \end{list}

 \item Construa gramáticas para as seguintes linguagens:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}}
			  \item $\{{\tt 0}\}\{{\tt 11}\}^*\{{\tt 0}\}$;
        \item $\{w\in\{{\tt a},{\tt b}\}^*\,|\, \mbox{ o número de {\tt a}s em $w$ é par}\}$;
        \item $\{{\tt a}^n{\tt b}^k\,|\, n>k\}$;
        \item $\{xx^R\,|\, x\in\{{\tt a},{\tt b}\}^*\}$.
       \end{list}

 \item Construa AFDs que reconheçam:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}}
        \item $\{{\tt 0},{\tt 1}\}^*-\{{\tt 0},{\tt 01},{\tt 10}\}$;
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, w \mbox{ tem número par de {\tt 0}s e um único {\tt 1}}\}$.
       \end{list}
			
 \item Sejam:
       \begin{itemize}\setlength{\parsep}{0.01mm}\setlength{\itemsep}{0.01mm}
        \item $L_1=\{{\tt 0},{\tt 1}\}^*\{{\tt 1}\}\{{\tt 0},{\tt 1}\}^*$;
        \item $L_2=\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, w \mbox{ contém número par de {\tt 0}s}\}$.
       \end{itemize}
       Construa AFDs que reconheçam:
       \begin{list}{\bf\alph{conta})}{\usecounter{conta}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}}
        \item $L_1$;
        \item $L_2$;
        \item $L_1-L_2$. Para isto, faça o produto dos autômatos que reconhecem $L_1$ e $\overline{L_2}$.
       \end{list}

 \item Seja o AFN com o diagrama de estados:

      \mbox{\setlength{\unitlength}{1mm}
       \begin{picture}(65,45)(-20,5)
        \gasset{Nw=6, Nh=6, Nmr=3, fillgray=0.9, loopdiam=4}

        \node[Nmarks=i, iangle=180](1)(10,25){1}
        \node(2)(25,35){2}
        \node(3)(25,15){3}
        \node[Nmarks=r](4)(40,25){4}
        \node[Nmarks=i, iangle=0](5)(55,25){5}

        \drawedge(1,2){\tt 0}
        \drawedge(1,3){\tt 1}
        \drawloop[loopangle=90](2){{\tt 0},{\tt 1}}
        \drawedge(2,4){\tt 1}
        \drawloop[loopangle=270](3){{\tt 0},{\tt 1}}
        \drawedge(3,4){\tt 0}
        \drawedge(5,4){\tt 0}
       \end{picture}
			}
			
        \hfill {[\emph{continua no verso}]} \newpage

        Obtenha um AFD equivalente utilizando o método de construção de subconjuntos.
 \item Seja o AFN$\lambda$:

              \mbox{\setlength{\unitlength}{1mm}
               \begin{picture}(100,25)\setlength{\unitlength}{1mm}
               \gasset{Nw=6, Nh=6, Nmr=6, ELdist=0.5, loopdiam=5, fillgray=0.9}

               \node[Nmarks=i](1)(20,15){1}
               \node(2)(30,8){2}
               \node(3)(40,15){3}

               \drawedge[curvedepth=-2,ELside=r](1,2){\tt 0}
               \drawedge[curvedepth=3](1,3){\tt 1}
               \drawedge[curvedepth=2](2,3){\tt 1}
               \drawloop[loopangle=90](3){\tt 1}
               \drawedge[curvedepth=2](3,2){\tt 0}

               \node[Nmarks=r](4)(65,15){4}
               \node(5)(80,15){5}

               \drawloop[loopangle=90](4){\tt 0}
               \drawedge[curvedepth=3](4,5){\tt 1}
               \drawedge[curvedepth=3](5,4){\tt 0}
               \drawedge[curvedepth=0](3,4){$\lambda$}
               \end{picture}
                      }
	
						 Obtenha um AFN equivalente usando a técnica para eliminação de transições $\lambda$. Mostre o cálculo de $\delta'(e,a)$ para cada par $(e,a)$ tal que $\delta'(e,a)\not=\delta(e,a)$, em que $\delta$ é a função de transição do AFN$\lambda$ e $\delta'$ é a função de transição do AFN obtido.
\end{enumerate}
\end{document}