\documentclass[12pt,a4paper]{report}

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

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


\newcounter{conta}
\pagestyle{empty}
\begin{document}
 
\noindent Pós-Graduação em Ciência da Computação \hfill DCC/ICEx/UFMG \\
\noindent \emph{Teoria de Linguagens}
 \hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2018 \\
\noindent Professor: Newton José Vieira \\
\noindent \emph{Primeira Prova}/Solução do professor \hfill 17/4/2018

\vspace*{3mm}
\begin{enumerate}
 \item {\footnotesize Descreva as linguagens a seguir usando apenas \textit{conjuntos finitos} e operações de \textit{união},
       \textit{concatenação} e \textit{fecho de Kleene}.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, n_{\tt 0}(w)>0 \mbox{ e } n_{\tt 1}(w)>0\}$.
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, n_{\tt 0}(w) \mbox{ é par}\}$.
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, n_{\tt 0}(w)\mbox{ mod } 3 = 0\}$.
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, {\tt 01} \mbox{ não é prefixo de } w\}$.
       \end{list}}

       \emph{Solução:}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt 0},{\tt 1}\}^*\{{\tt 01},{\tt 10}\}\{{\tt 0},{\tt 1}\}^*$
        \item $\{{\tt 1}\}^*(\{{\tt 0}\}\{{\tt 1}\}^*\{{\tt 0}\}\{{\tt 1}\}^*)^*$
        \item $\{{\tt 1}\}^*(\{{\tt 0}\}\{{\tt 1}\}^*\{{\tt 0}\}\{{\tt 1}\}^*\{{\tt 0}\}\{{\tt 1}\}^*)^*$
        \item $\{\lambda,{\tt 0}\}\cup\{{\tt 00,1}\}\{{\tt 0},{\tt 1}\}^*$
       \end{list}

 \item {\footnotesize Obtenha gramáticas para as linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt 00}\}\{{\tt 00},{\tt 1}\}^*\{{\tt 1}\}$.
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, n_{\tt 0}(w) \mbox{ é par}\}$.
        \item $\{{\tt 0}^n{\tt 1}^k\,|\, n\geq k\}$.
        \item $\{{\tt 0}^{n}{\tt 1}^{2k}{\tt 0}^{3n}\,|\, n,k\in\mathbb{N}\}$.
       \end{list}}

       \emph{Solução:}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item \begin{enumerate}
               \item[\ ] $P \,\rightarrow\, {\tt 00}X {\tt 1}$
               \item[\ ] $X \,\rightarrow\, {\tt 00}X \,|\, {\tt 1}X \,|\, \lambda$
              \end{enumerate}
        \item \begin{enumerate}
               \item[\ ] $P \,\rightarrow\, {\tt 1}P \,|\, {\tt 0}I \,|\, \lambda$
               \item[\ ] $I \,\rightarrow\, {\tt 1}I \,|\, {\tt 0}P$
              \end{enumerate}
        \item \begin{enumerate}
               \item[\ ] $P \,\rightarrow\, {\tt 0}P \,|\, {\tt 0}P{\tt 1} \,|\, \lambda$
              \end{enumerate}
        \item \begin{enumerate}
               \item[\ ] $Z \,\rightarrow\, {\tt 0}Z{\tt 000} \,|\, U$
               \item[\ ] $U \,\rightarrow\, {\tt 11}U \,|\, \lambda$
              \end{enumerate}
       \end{list}
             
 \item {\footnotesize Obtenha AFDs para as linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt 00}\}\{{\tt 00},{\tt 1}\}^*\{{\tt 1}\}$.
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, {\tt 01} \mbox{ não é prefixo de } w\}$.
       \end{list}}

       \emph{Solução:}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item \

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

               \node[Nmarks=i](1)(20,5){}
               \node(2)(40,5){}
               \node(3)(60,0){}
               \node[Nmarks=r](4)(80,10){}

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

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

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

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

 \item {\footnotesize Seguem diagramas de estado incompletos de dois AFDs, um que reconhece $X=\{{\tt 0}\}^*\{{\tt 1}\}$ e outro que
       reconhece $Y=\{{\tt 1}\}^*\{{\tt 0}\}$:
       \begin{center}
       \begin{picture}(120,10)
        \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}
        \node[Nmarks=i](1)(20,0){1}
        \node[Nmarks=r](2)(40,0){2}

        \node[Nmarks=i](3)(70,0){1}
        \node[Nmarks=r](4)(90,0){2}

        \drawloop[loopangle=90](1){\tt 0}
        \drawedge[curvedepth=0](1,2){\tt 1}
        \drawloop[loopangle=90](3){\tt 1}
        \drawedge[curvedepth=0](3,4){\tt 0}
       \end{picture}
       \end{center}
       Faça o produto dos dois (não esquecendo estados de erro) e aponte que estados seriam finais para o reconhecimento de:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $X\cap Y$. \hspace{1cm} (b) $X\cup Y$. \hspace{1cm} (c) $X-Y$.
       \end{list}}

       \emph{Solução:} \ 
			
       \begin{picture}(90,37)
        \gasset{Nw=8, Nh=6, Nmr=7, fillgray=0.9, loopdiam=4}
        \node[Nmarks=i](11)(20,19){11}
        \node(12)(30,29){12}
        \node(21)(30,9){21}
        \node(1e)(48,36){1e}
        \node(e2)(55,14){e2}
        \node(2e)(55,24){2e}
        \node(e1)(48,2){e1}
        \node(ee)(70,19){ee}
        \node(22)(70,36){22}

        \drawedge[curvedepth=0](11,12){\tt 0}
        \drawedge[curvedepth=0,ELside=r](11,21){\tt 1}
        \drawedge[curvedepth=0](12,1e){\tt 0}
        \drawedge[curvedepth=0](12,2e){\tt 1}
        \drawedge[curvedepth=0](1e,2e){\tt 1}
        \drawloop[loopangle=0](1e){\tt 0}
        \drawedge[curvedepth=0](2e,ee){{\tt 0},{\tt 1}}
        \drawedge[curvedepth=0](21,e2){\tt 0}
        \drawedge[curvedepth=0,ELside=r](21,e1){\tt 1}
        \drawedge[curvedepth=0,ELside=r](e1,e2){\tt 0}
        \drawloop[loopangle=0](e1){\tt 1}
        \drawedge[curvedepth=0,ELside=r](e2,ee){{\tt 0},{\tt 1}}
        \drawloop[loopangle=0](ee){{\tt 0},{\tt 1}}
        \drawedge[curvedepth=0](22,ee){{\tt 0},{\tt 1}}
       \end{picture}

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item 22. \hspace{1cm} (b) 21, 22, 2e, 12, e2. \hspace{1cm} (c) 21, 2e.
       \end{list}


 \item {\footnotesize Faça um AFN de, \emph{no máximo 4 estados}, que reconheça o conjunto de palavras de $\{{\tt a},{\tt b},{\tt c}\}^*$
       em que o último símbolo não ocorra antes, ou seja, $\{{\tt b},{\tt c}\}^*\{{\tt a}\}\cup\{{\tt a},{\tt c}\}^*
			 \{{\tt b}\}\cup\{{\tt a},{\tt b}\}^*\{{\tt c}\}$.}

       \emph{Solução:} \ 

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

               \node[Nmarks=i](1a)(20,35){1a}
               \node[Nmarks=i](1b)(20,20){1b}
               \node[Nmarks=i](1c)(20,5){1c}
               \node[Nmarks=r](2)(40,20){2}

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

 \item {\footnotesize Seja o AFN com o diagrama de estados a seguir:
       \begin{center}
       \begin{picture}(70,35)
        \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}
        \node[Nmarks=i](1)(20,25){1}
        \node[Nmarks=i](2)(20,5){2}
        \node[Nmarks=r](3)(40,15){3}

        \drawloop[loopangle=90](1){\tt 0}
        \drawedge[curvedepth=0](1,3){\tt 1}
        \drawloop[loopangle=270](2){\tt 1}
        \drawedge[curvedepth=0, ELside=r](2,3){\tt 0}
       \end{picture}
       \end{center}
       Apresente o diagrama de estados completo de um AFD equivalente usando o método visto em aula
			 (construção de subconjuntos).}

       \emph{Solução:} \ 

       \begin{picture}(90,32)
        \gasset{Nw=8, Nh=6, Nmr=7, fillgray=0.9, loopdiam=4}
        \node[Nmarks=i](12)(20,15){12}
        \node[Nmarks=r](13)(30,25){13}
        \node[Nmarks=r](23)(30,5){23}
        \node[Nmarks=r](3)(40,15){3}
        \node(1)(48,28){1}
        \node(2)(48,2){2}
        \node(e)(60,15){$\emptyset$}

        \drawedge[curvedepth=0](12,13){\tt 0}
        \drawedge[curvedepth=0,ELside=r](12,23){\tt 1}
        \drawedge[curvedepth=0](13,1){\tt 0}
        \drawedge[curvedepth=0](13,3){\tt 1}
        \drawedge[curvedepth=0,ELside=r](23,2){\tt 1}
        \drawedge[curvedepth=0,ELside=r](23,3){\tt 0}
        \drawloop[loopangle=0](1){\tt 0}
        \drawedge[curvedepth=0](1,3){\tt 1}
        \drawloop[loopangle=0](2){\tt 1}
        \drawedge[curvedepth=0, ELside=r](2,3){\tt 0}
       \drawedge[curvedepth=0](3,e){{\tt 0},{\tt 1}}
        \drawloop[loopangle=0](e){{\tt 0},{\tt 1}}
       \end{picture}

 \item{\footnotesize Seja o AFN$\lambda$ com o diagrama de estados a seguir:
       \begin{center}
       \begin{picture}(90,10)
        \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}
        \node[Nmarks=i](1)(20,0){1}
        \node(2)(40,0){2}
        \node[Nmarks=r](3)(60,0){3}

        \drawloop[loopangle=90](1){\tt a}
        \drawedge[curvedepth=0](1,2){$\lambda$}
        \drawloop[loopangle=90](2){\tt b}
        \drawedge[curvedepth=0](2,3){$\lambda$}
        \drawloop[loopangle=90](3){\tt c}
       \end{picture}
       \end{center}
       Construa um AFN equivalente usando o método visto em aula. Comece exibindo $f\lambda(e)$ para cada estado $e$.}

       \emph{Solução:}

       $f\lambda(1)=\{1,2,3\}$,  $f\lambda(2)=\{2,3\}$,  $f\lambda(3)=\{3\}$.

       \begin{picture}(90,20)
        \gasset{Nw=6, Nh=6, Nmr=3, fillgray=0.9, loopdiam=4, iangle=270}
        \node[Nmarks=i](1)(20,5){1}
        \node[Nmarks=i](2)(40,0){2}
        \node[Nmarks=ir](3)(60,5){3}

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

\end{enumerate}

\end{document}
