\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 {\footnotesize 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}}

       \emph{Solução}: \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item Conjunto das palavras cujo penúltimo símbolo é {\tt 1}.
        \item Conjunto das palavras que começam com {\tt 0} ou terminam com {\tt 1}.
        \item Conjunto das palavras em que todo {\tt 0} (caso haja algum) é seguido de {\tt 1}.
        \item Conjunto das palavras com um número ímpar de {\tt 1}s.
       \end{list}


 \item {\footnotesize 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}}

       \emph{Solução}: \begin{list}{\alph{conta})}{\usecounter{conta}}
         \item \begin{enumerate}
                \item[\ ] $P \,\rightarrow\, {\tt 0}X {\tt 0}$
                \item[\ ] $X \,\rightarrow\, {\tt 11}X \,|\, \lambda$
               \end{enumerate}
         \item \begin{enumerate}
                \item[\ ] $P \,\rightarrow\, {\tt a}I \,|\, {\tt b}P \,|\, \lambda$
                \item[\ ] $I \,\rightarrow\, {\tt a}P \,|\, {\tt b}I$
               \end{enumerate}

         \item \begin{enumerate}
                \item[\ ] $X \,\rightarrow\, {\tt a}X \,|\, {\tt a}X{\tt b} \,|\, {\tt a}$
               \end{enumerate}

         \item \begin{enumerate}
                \item[\ ] $X \,\rightarrow\, {\tt a}X{\tt a} \,|\, {\tt b}X{\tt b}
                           \,|\, \lambda$
               \end{enumerate}
        \end{list}

 \item {\footnotesize 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}}
			
       \emph{Solução}:\begin{list}{\alph{conta})}{\usecounter{conta}}

       \item \  

              \mbox{\setlength{\unitlength}{1mm}
              \begin{picture}(120,20)\setlength{\unitlength}{1mm}
               \gasset{Nw=5, Nh=5, Nmr=2.5, loopdiam=6}

               \node[Nmarks=ir](i)(20,12){}
               \node(1)(35,19){}
               \node[Nmarks=r](2)(35,5){}
               \node(3)(50,12){}
               \node[Nmarks=r](4)(65,12){}

               \drawedge[curvedepth=0](i,1){{\tt 0}}
               \drawedge[curvedepth=0, ELside=r](i,2){{\tt 1}}
               \drawedge[curvedepth=0](1,3){{\tt 1}}
               \drawedge[curvedepth=0,ELside=r](2,3){{\tt 0}}
               \drawedge[curvedepth=6](1,4){{\tt 0}}
               \drawedge[curvedepth=0](3,4){{\tt 0},{\tt 1}}
               \drawedge[curvedepth=-6,ELside=r](2,4){{\tt 1}}
               \drawloop[loopangle=0](4){{\tt 0},{\tt 1}}
              \end{picture}
             } \\

       \item \

              \mbox{\setlength{\unitlength}{1mm}
              \begin{picture}(120,20)\setlength{\unitlength}{1mm}
               \gasset{Nw=6, Nh=6, Nmr=3, loopdiam=6}

               \node[Nmarks=i](i)(20,20){}
               \node(1)(20,5){}
               \node[Nmarks=r](2)(40,20){}
               \node(3)(40,5){}

               \drawedge[curvedepth=3](i,1){\tt 0}
               \drawedge[curvedepth=0](i,2){\tt 1}
               \drawedge[curvedepth=3](1,i){\tt 0}
               \drawedge[curvedepth=0](1,3){\tt 1}
               \drawedge[curvedepth=3](2,3){\tt 0}
               \drawedge[curvedepth=3](3,2){\tt 0}

              \end{picture}
             }
      \end{list}

 \item {\footnotesize 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}}

       \emph{Solução}: \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item \ 
        
              \mbox{\setlength{\unitlength}{1mm}
               \begin{picture}(100,15)
                \gasset{Nw=6, Nh=6, Nmr=3, %fillcolor=Gray,
								        fillgray=0.9, loopdiam=4}

                \node[Nmarks=i, iangle=180](A)(25,10){A}
                \node[Nmarks=r](B)(45,10){B}

                \drawedge[curvedepth=0](A,B){{\tt 1}}
                \drawloop[loopangle=90](A){{\tt 0}}
                \drawloop[loopangle=90](B){{\tt 0},{\tt 1}}
               \end{picture}
              }

        \item \ 
        
              \mbox{\setlength{\unitlength}{1mm}
               \begin{picture}(100,15)
                \gasset{Nw=6, Nh=6, Nmr=3, %fillcolor=Gray,
								        fillgray=0.9, loopdiam=4}

                \node[Nmarks=ir, iangle=180](1)(25,10){1}
                \node(2)(45,10){2}

                \drawloop[loopangle=90](1){{\tt 1}}
                \drawedge[curvedepth=3](1,2){{\tt 0}}
                \drawloop[loopangle=90](2){{\tt 1}}
                \drawedge[curvedepth=3](2,1){{\tt 0}}
               \end{picture}
              }

        \item \ 
        
              \mbox{\setlength{\unitlength}{1mm}
               \begin{picture}(100,30)
                \gasset{Nw=8, Nh=6, Nmr=3, %fillcolor=Gray,
								        fillgray=0.9, loopdiam=4}

                \node[Nmarks=i, iangle=180](A1)(25,25){A1}
                \node(B1)(25,10){B1}
                \node(A2)(45,25){A2}
                \node[Nmarks=r](B2)(45,10){B2}

                \drawedge[curvedepth=3](A1,A2){{\tt 0}}
                \drawedge[curvedepth=0](A1,B1){{\tt 1}}
                \drawedge[curvedepth=3](A2,A1){{\tt 0}}
                \drawedge[curvedepth=0](A2,B2){{\tt 1}}
                \drawloop[loopangle=270](B1){{\tt 1}}
                \drawedge[curvedepth=3](B1,B2){{\tt 0}}
                \drawloop[loopangle=270](B2){{\tt 1}}
                \drawedge[curvedepth=3](B2,B1){{\tt 0}}
               \end{picture}
              }

       \end{list}

 \item {\footnotesize Seja o AFN com o diagrama de estados:
       \begin{center}
       \begin{picture}(65,45)
        \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}
			\end{center}
       Obtenha um AFD equivalente utilizando o método de construção de subconjuntos.}

       \emph{Solução}:

              \mbox{\setlength{\unitlength}{1mm}
               \begin{picture}(65,40)
                \gasset{Nw=8, Nh=6, Nmr=7, %fillcolor=Gray,
								        fillgray=0.9, loopdiam=4}

                \node[Nmarks=i, iangle=180](15)(10,20){15}
                \node[Nmarks=r](24)(25,30){24}
                \node(3)(25,10){3}
                \node(2)(40,30){2}
                \node[Nmarks=r](34)(40,10){34}

                \drawedge(15,24){\tt 0}
                \drawedge(15,3){\tt 1}
                \drawloop[loopangle=90](24){\tt 1}
                \drawedge[curvedepth=3](24,2){\tt 0}
                \drawloop[loopangle=270](3){\tt 1}
                \drawedge[curvedepth=3](3,34){\tt 0}
                \drawloop[loopangle=90](2){\tt 0}
                \drawedge[curvedepth=3](2,24){\tt 1}
                \drawloop[loopangle=270](34){\tt 0}
                \drawedge[curvedepth=3](34,3){\tt 1}
               \end{picture}
							}

 \item {\footnotesize 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$.}
						
          \emph{Solução}:

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

               \node[Nmarks=i](1)(20,25){1}
               \node(2)(30,18){2}
               \node(3)(40,25){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)(50,10){4}
               \node(5)(65,10){5}

               \drawloop[loopangle=270](4){\tt 0}
               \drawedge[curvedepth=3](4,5){\tt 1}
               \drawedge[curvedepth=3](5,4){\tt 0}

               \drawedge[curvedepth=-12,ELside=r](1,4){\tt 1}
               \drawedge[curvedepth=-4](2,4){\tt 1}
               \drawedge[curvedepth=0,ELside=r](3,4){\tt 1}
               \end{picture}
                      }
											
							Para $e=1, 2, 3$: $\delta'(e,1)=f\lambda(\delta(e,1))=f\lambda(\{3\})=\{3,4\}$. 
\end{enumerate}
\end{document}