\documentclass[11pt,a4paper]{article}

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

\usepackage{verbatim}
\usepackage{gastex}
\usepackage[usenames]{color}


\newcounter{conta}
\newcounter{conta2}
\pagestyle{empty}

\begin{document}
 
\vspace*{15mm}
\noindent P\'os-Gradua\c{c}\~ao em Ci\^{e}ncia da Computa\c{c}\~{a}o
 \hfill DCC/ICEx/UFMG \\
\noindent {\it Teoria de Linguagens}
 \hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2011 \\
\noindent Professor: Newton Jos\'{e} Vieira \\
\noindent {\bf Primeira Prova} \hfill 20/09/2011

\vspace*{3mm}
\begin{flushleft}
 As duas primeiras questões valem 3 e as outras valem 4 pontos cada uma.
\end{flushleft}
\vspace*{1mm}
\begin{enumerate}
 \item Seja o alfabeto $\Sigma=\{{\tt 0},{\tt 1}\}$ e as linguagens $A=\Sigma\{{\tt 1}\}\Sigma^*$
       e $B=\Sigma^*\{{\tt 1}\}$. Usando uma
       express\~ao obtida a partir de \textit{conjuntos finitos} e opera\c{c}\~oes dentre \textit{uni\~ao},
       \textit{concatena\c{c}\~ao} e \textit{fecho de Kleene}, expresse:
       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item $\overline{A}$.
        \item $A\cap B$.
        \item $B-A$.
       \end{list}

 \item Apresente o digrama de estados de um AFD de que reconheça ``\emph{o conjunto das palavras em que o símbolo
       na posição $i$ é diferente do símbolo na posição $i+2$, para $i\geq 1$}''. Considere que o símbolo
       na posição 1 de uma palavra é seu primeiro símbolo, o símbolo na posição 2 é o segundo, e assim por diante.

 \item Seja o AFN com o seguinte diagrama de estados:
       \begin{center}
        \begin{picture}(60,15) \setlength{\unitlength}{1mm}
         \gasset{Nw=6, Nh=6, Nmr=3, loopdiam=6}

         \node[Nmarks=i, iangle=0](i1)(50,5){$i_1$}
         \node[Nmarks=i](i0)(10,5){$i_0$}
         \node[Nmarks=r](f)(30,5){$f$}
      
         \drawedge[curvedepth=0](i0,f){{\tt 0}}
         \drawloop[loopangle=90](i0){{\tt 1}}
         \drawedge[curvedepth=0, ELside=r](i1,f){{\tt 1}}
         \drawloop[loopangle=90](i1){{\tt 0}}
        \end{picture}
       \end{center}
      \begin{list}{\alph{conta})}{\usecounter{conta}}
       \item Que linguagem \'e reconhecida pelo AFN em quest\~ao?
       \item Obtenha um AFD equivalente pelo m\'etodo de constru\c{c}\~ao-de-subconjuntos (aquele em que
             cada estado do AFD é um subconjunto dos estados do AFN).
      \end{list}

 \item Seja o AFN-$\lambda$ com o seguinte diagrama de estados:
       \begin{center}
        \begin{picture}(60,15) \setlength{\unitlength}{1mm}
         \gasset{Nw=6, Nh=6, Nmr=3, loopdiam=6}

         \node[Nmarks=i, iangle=180](1)(10,5){1}
         \node[Nmarks=i](2)(30,5){2}
         \node[Nmarks=r](3)(50,5){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$,{\tt b}}
         \drawloop[loopangle=90](3){{\tt c}}
        \end{picture}
       \end{center}
       Obtenha um AFN equivalente usando o método visto em aula. Explicite, para
       cada estado $e$ e símbolo $s$, como é feito o cálculo de $\delta'(e,s)$ nos casos em que
       $\delta'(e,s)\not=\delta(e,s)$ ($\delta$ é a função de transição do AFN-$\lambda$ e $\delta'$ é a função de
       transição do AFN sendo obtido).

 \item Sejam $L$ uma linguagem regular qualquer, $L_1=\{{\tt 0}\}^*$ e $L_2=\{{\tt 0}^k{\tt 1}^{k+1}\,|\, k\geq 0\}$.
       Para cada linguagem a seguir, mostre que ela \'e regular ou que n\~ao \'e ou que pode ser ou não ser:
       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item $L_1L_2$.
        \item $L\cap L_1$.
        \item $L\cap L_2$.
        \item $L-L_1$.
       \end{list}
\end{enumerate}

\end{document}
