\documentclass[11pt, a4paper]{article}
 
\usepackage[brazilian]{babel}
\usepackage[T1]{fontenc} 

\usepackage{fullpage}
 
\newcounter{conta}
\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 1993
 
\noindent Professor: Newton Jos\'{e} Vieira
 
\noindent \underline{Terceira Prova}
 
%\vspace*{3mm}
\begin{enumerate}
 \item Seja a gram\'atica regular $G = (\{S,A,B\}, \{a,b\}, P, S)$, onde $P$
       consta das regras:
       \begin{enumerate}
        \item[\ \ \ ] $S \rightarrow a S \,\,|\,\, b S \,\,|\,\, a A$
        \item[\ \ \ ] $A \rightarrow a \,\,|\,\, b B$
        \item[\ \ \ ] $B \rightarrow b A$
       \end{enumerate}
       Construa um aut\^omato finito n\~ao determin\'{\i}stico que aceite
       $L(G)$, utilizando o m\'etodo visto no curso.
 \item Prove que a linguagem $\{a^ib^j \,\,|\,\, i > j\}$ n\~ao \'e regular.
 \item Construa um aut\^omato a pilha para a linguagem $\{a^ib^jc^i \,\,|\,\,
       i,j \geq 0\}$.
 \item Seja o aut\^omato a pilha $M = (\{q_0, q_1\},\{0, 1\}, \{A\}, \delta,
       q_0, \{q_0, q_1\})$, onde $\delta$ \'e dada por:
	\begin{enumerate}
	 \item[\ \ \ ] $\delta(q_0,0,\lambda) = \{[q_0,A]\}$
	 \item[\ \ \ ] $\delta(q_0,1,A) = \{[q_1,\lambda]\}$
	 \item[\ \ \ ] $\delta(q_1,1,A) = \{[q_1,\lambda]\}$
	\end{enumerate}
       Construa uma gram\'atica livre do contexto $G$ que gere $L(M)$,
       utilizando o m\'etodo visto no curso.
 \item Construa uma M\'aquina de Turing com alfabeto $\{a,b,c\}$ que aceite os
       {\em strings\/} nos quais o primeiro $a$ \'e precedido por $b$ e o
       primeiro $c$ \'e precedido por $a$. Exemplos de {\em strings\/} a serem
       aceitos (o primeiro $a$ e o primeiro $c$ est\~ao grifados):
 
	\begin{tabular}{clcl}
	  \ \ \ & $\lambda$ & \ \ \ \ & $bb\underline{a}a\underline{c}a$ \\
	        & $bbb$     & & $b\underline{a}a\underline{c}bbbb$\\
	        & $b\underline{a}$      & &
		 $bbb\underline{a}ba\underline{c}bbcc$\\
	        & $b\underline{a}\underline{c}$ & & $bbb\underline{a}
		\underline{c}bcbca$
	\end{tabular}
 
       Exemplos de {\em strings\/} a \underline{n\~ao} serem aceitos:
 
	\begin{tabular}{clcl}
	  \ \ \ & $a$ & \ \ \ \ & $bc$ \\
	        & $c$      & & $abc$\\
	        & $ac$     & & $babc$\\
	        & $aaaaaa$ & & $bbbaabbc$
	\end{tabular}
 
\end{enumerate}
 
\end{document}
\endinput
\end
 
