\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} \hfill 17/4/2018

\vspace*{3mm}
\begin{enumerate}
 \item (4 pontos) 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}

 \item (4 pontos) 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}

 \item (4 pontos) 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}
 \item (3 pontos) 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}
 \item (3 pontos) 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}\}$.

\vfill
\hfill {\footnotesize \emph{Segue no verso}} $\Rightarrow$
\pagebreak

 \item (3 pontos) 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).
 \item (3 pontos) 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$.

\end{enumerate}

\end{document}
