\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{2}^{\mbox{\underline{o}}}$ semestre de 1996
 
\noindent Professor: Newton Jos\'{e} Vieira
 
\noindent \underline{Terceira Prova/Especial} \hfill 18/11/96
 
\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}
 
\begin{enumerate}
 \item Construa aut\^{o}matos finitos determin\'{\i}sticos para reconhecer as seguintes
       linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item {\boldmath $(01^+)^*010$}
        \item o conjunto de {\em strings\/} sobre $\{0,1\}$, que tenham no
              m\'{\i}nimo dois $1$'s e no m\'{a}ximo dois $0$'s.
       \end{list}
 \item Usando a t\'{e}cnica do grafo de express\~{o}es, determine uma express\~{a}o regular
       que denote a linguagem reconhecida pelo aut\^{o}mato:
       \[M=(\{q_0,q_1,q_2,q_3,q_4\},\{0,1\},\delta,q_0,\{q_0,q_3\})\mbox{,}\]
       onde $\delta$ \'{e} dada por:
       \begin{center}
        \begin{tabular}{c|cc}
         $\delta$ & $0$ & $1$ \\ \hline
         $q_0$ & $q_1$ & $q_4$ \\
         $q_1$ & $q_0$ & $q_2$ \\
         $q_2$ & $q_2$ & $q_2$ \\
         $q_3$ & $q_2$ & $q_4$ \\
         $q_4$ & $q_2$ & $q_3$ 
        \end{tabular}
       \end{center}
       N\~{a}o simplifique a express\~{a}o obtida.
 \item Prove que a linguagem $\{w\in\{a,b\}^* \,\,|\,\, \mbox{\it $w$ tem algum
       prefixo que cont\'{e}m mais $b$'s que $a$'s}\}$ n\~ao \'e regular.
 \item Sejam $L_1$ e $L_2$ duas linguagens regulares com alfabeto $\{0,1\}$. Prove
       que as seguintes afirmativas s\~ao falsas:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Se $L_1\subseteq L_2$ e $L_1$ n\~ao \'e regular, ent\~ao $L_2$ n\~ao
              \'e regular.
        \item Se $L_1\subseteq L_2$ e $L_2$ n\~ao \'e regular, ent\~ao $L_1$ n\~ao
              \'e regular.
        \item Se $L_1$ e $L_2$ n\~ao s\~ao regulares, ent\~ao $L_1\cup L_2$ n\~ao
              \'e regular.
        \end{list}
 \item Construa um aut\^omato a pilha que reconhe\c ca a linguagem
       \[\{a^ib^jc^k \,\,|\,\, \mbox{\it $i>j$ ou $j>k$ (ou ambos)}\}\mbox{.}\]
 \item No m\'etodo visto em aula, a gram\'atica que se obt\'em para gerar a
       linguagem reconhecida por um aut\^omato a pilha, tem vari\'aveis da
       forma $\langle q_i, A, q_j \rangle$.
       Descreva, formal ou informalmente, quais s\~ao os {\it strings\/} $w\in
       \Sigma^*$ tais que: \[\langle q_i, A, q_j \rangle 
       \stackrel{*}{\Longrightarrow} w\mbox{.}\]

\end{enumerate}
 
\end{document}
\endinput
\end
 
 
