\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} \hfill 31/10/96
 
\begin{description}
 \item[Dura\c{c}\~{a}o:] 1 hora e 40 minutos.
 \item[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 $(00\cup 1)^*101$}
        \item o conjunto de {\em strings\/} sobre $\{0,1\}$, de tamanho \'{\i}mpar,
              que tenham 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,\},\{0,1,2\},\delta,q_0,\{q_2\})\mbox{,}\]
       onde $\delta$ \'{e} dada por:
       \begin{center}
        \begin{tabular}{c|ccc}
         $\delta$ & $0$ & $1$ & $2$ \\ \hline
         $q_0$ & $\{q_0,q_1\}$ & $\phi$ & $\phi$ \\
         $q_1$ & $\phi$ & $\{q_1\}$ & $\{q_2\}$ \\
         $q_2$ & $\{q_0\}$ & $\{q_1\}$ & $\{q_2\}$ 
        \end{tabular}
       \end{center}
       N\~{a}o simplifique a express\~{a}o obtida.
 \item Prove que a linguagem $\{ww^R \,\,|\,\, w\in\{a,b\}^*\}$ n\~{a}o \'{e} regular.
 \item Seja $M=(Q,\Sigma,\delta,q_0,F)$ um aut\^{o}mato finito determin\'{\i}stico.
       Mostre como construir um aut\^{o}mato finito determin\'{\i}stico $M'$ tal que:
       \[L(M')=\{u \,\,\,|\,\,\, uv\in L(M)\}\mbox{;}\]
       ou seja, $L(M')$ \'{e} a linguagem de todos os prefixos de {\em strings\/}
       de $L(M)$.
 \item Construa aut\^omatos a pilha para as linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{a^ib^j \,\,|\,\, i>j\}$
        \item $\{w\in\{a,b\}^* \,\,|\,\, \mbox{\it $w$ tem algum prefixo que
               cont\'{e}m mais $b$'s que $a$'s}\}$
       \end{list}
 \item Descreva um algoritmo que obtenha um aut\^{o}mato a pilha que reconhe\c{c}a a
       linguagem gerada por uma gram\'{a}tica livre do contexto (qualquer).
 
\end{enumerate}
 
\end{document}
\endinput
\end
 
 
