\documentstyle[12pt]{artigo}
 
\newcounter{conta}
\newcounter{conta2}
\pagestyle{empty}
\begin{document}
 
\noindent Bacharelado em Ci\^{e}ncia da Computa\c{c}\~{a}o
\hfill DCC/ICEx/UFMG
 
\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 1997
 
\noindent Professor: Newton Jos\'{e} Vieira
 
\noindent \underline{Terceira Prova} \hfill 27/05/97

\vspace*{2mm}
\begin{description}
 \item[Dura\c{c}\~{a}o:] 1 hora e 40 minutos. {\bf Valores das quest\~{o}es:}
  3 pontos cada uma.
\end{description}

\vspace*{1mm}
\begin{enumerate}
 \item Seja $L=\{w \in \{0,1\}^* \,\,|\,\, |w|\geq 4$ e o segundo e o
       pen\'ultimo s\'{\i}mbolos s\~ao ambos o s\'{\i}mbolo 1$\}$.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Determine um aut\^omato finito n\~ao-determin\'{\i}stico de, no
              m\'aximo, 5 estados, que reconhe\c ca $L$.
        \item Determine um aut\^omato finito determin\'{\i}stico que
              reconhe\c ca $L$.
       \end{list}
 
 \item Seja o aut\^omato finito $M=(\{q_0,q_1,q_2,q_3\},
       \{a,b\},\delta,q_0,\{q_2\})$, onde $\delta$ \'e dada pela tabela:
       \begin{center}
       \begin{tabular}{c|cc}
        $\delta$ & $a$       & $b$ \\ \hline
        $q_0$ & $\{q_1\}$ & $\{q_3\}$ \\
        $q_1$ & $\{q_1\}$ & $\{q_0,q_2\}$ \\
        $q_2$ & $\{q_1\}$ & $\{q_2\}$ \\
        $q_3$ & $\{q_3\}$ & $\{q_3\}$
       \end{tabular}
       \end{center}
       Determine uma express\~ao regular que denote $L(M)$.
 
 \item Sejam $R_1$ e $R_2$ conjuntos regulares, e $L$ uma linguagem livre do
       contexto. Mostre que:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $R_1-R_2$ \'e conjunto regular.
        \item $R_1-L$ pode n\~ao ser linguagem livre do contexto.
       \end{list}

 \item Seja $L=\{xy \in \{0,1\}^* \,\,|\,\, |x|=|y|$ e o $i$-\'esimo
       s\'{\i}mbolo de $x$ \'e $1$ se, e somente se, o $i$-\'esimo s\'{\i}mbolo
       de $y$ \'e $0\}$. Por exemplo, os 7 menores s\'{\i}mbolos de $L$ s\~ao:
       $\lambda$, $01$, $10$, $0011$, $0110$, $1001$ e $1100$. Prove que $L$
       n\~ao \'e uma linguagem regular.
       
 \item Construa um {\it pushdown automaton\/} que reconhe\c ca $\{a^ib^j \,\,|
       \,\, 0\leq i\leq j\}$.

 \item Mostre que as linguagens livres do contexto s\~ao fechadas sob:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item concatena\c c\~ao
        \item reverso
       \end{list}

\end{enumerate}

\end{document}
\endinput
\end

                                                                  
