\documentclass[11pt,a4paper]{article}

\usepackage[portuguese]{babel}
\usepackage{verbatim}
\usepackage{fullpage}
%\usepackage{gastex}
%\usepackage[usenames]{color}

\newcounter{conta}
\pagestyle{empty}

\begin{document}
 
\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 2008 \\
\noindent Professor: Newton Jos\'{e} Vieira \\
\noindent {\bf Primeira Prova} \hfill 17/09/2008

\vspace*{5mm}
\noindent A quest\~ao 4 vale 2 pontos e as restantes valem 4 pontos cada uma.

\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}\}$. Para cada linguagem a seguir, enuncie em portugu\^es uma
       condi\c{c}\~ao necess\'aria e suficiente para que uma palavra perten\c{c}a \`a mesma,
       deixando impl\'{\i}cito que a palavra cont\'em apenas {\tt 0}s e {\tt 1}s, e iniciando
       com o n\'umero m\'{\i}nimo de s\'{\i}mbolos que ela tem. Por exemplo, uma condi\c{c}\~ao necess\'aria
       e suficiente para que uma palavra perten\c{c}a a $B\cap (\Sigma\Sigma)^*$ \'e: \emph{tem no
       m\'{\i}nimo dois s\'{\i}mbolos, tamanho par e termina em {\tt 1}}.
       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item $AB$.
        \item $A\cap B$.
        \item $A-B$.
        \item $B-A$.
       \end{list}

 \item Seja a linguagem $L=\{{\tt a}^n{\tt b}^i{\tt c}^j\,|\,i+j=n\}$.
       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item Prove que $L$ n\~ao \'e regular.
        \item Fa\c{c}a uma gram\'atica $G$ que gere $L$.
        \item Mostre, por meio de um esquema de deriva\c{c}\~ao, que toda palavra da forma
              ${\tt a}^n{\tt b}^i{\tt c}^j$, para $i+j=n$, \'e gerada por $G$.
       \end{list}

 \item Seja $L_1=\{{\tt 01},{\tt 10}\}^*$ e $L_2=\{{\tt 01}\}\{{\tt 0},{\tt 1}\}^*\{{\tt 10}\}$.
       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item Construa o diagrama de estados de um AFD $M_1$ que reconhe\c{c}a $L_1$.
        \item Construa o diagrama de estados de um AFD $M_2$ que reconhe\c{c}a $L_2$.
        \item Como um AFD que reconhe\c{c}a $L_1-L_2$ pode ser constru\'{\i}do a partir de $M_1$ e
              $M_2$? Fa\c{c}a refer\^encia a algum m\'etodo visto no curso e descreva em detalhes
              apenas o conjunto de estados, o estado inicial e os estados finais de tal AFD
              (n\~ao \'e preciso especificar as transi\c{c}\~oes).
       \end{list}

 \item Construa um AFN (sem transi\c{c}\~oes $\lambda$) que reconhe\c{c}a $X\{{\tt 01}\}^*$, sendo
       \[X=\{w\in\{{\tt 0},{\tt 1}\}^*\,|\,\eta(w) \mbox{ mod } 3 = 1\}\] onde $\eta(w)$
       \'e o n\'umero representado por $w$ na base 2.

 \item Responda sim ou n\~ao, justificando sua resposta:
       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item Para toda linguagem regular existe um AFN (sem transi\c{c}\~oes $\lambda$) com um
              \'unico estado final. 
        \item Para qualquer linguagem $L$, regular ou n\~ao, existem linguagens regulares $R_I$
              e $R_S$ tais que $R_I\subseteq L\subseteq R_S$.
        \item Se $L$ for n\~ao regular, $F\subseteq L$ e $F$ finita, $L-F$ pode ser regular ou n\~ao.
        \item O problema de determinar se uma linguagem regular, cujo alfabeto \'e $\Sigma$,
              cont\'em alguma palavra com a ocorr\^encia de todos os s\'{\i}mbolos de $\Sigma$
              \'e decid\'{\i}vel.
       \end{list}
\end{enumerate}

\end{document}
