\documentstyle[12pt]{artigo}
 
\begin{document}
 
\noindent Bacharelado em Ci\^{e}ncia da Computa\c{c}\~{a}o
\hfill ICEx/UFMG
 
\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao}

\section{Ementa}

Linguagens Formais. Decidibilidade.
 
\section{Programa}
 
\begin{itemize}
 \item Conceitos B\'asicos de Matem\'atica: conceitos b\'asicos de teoria dos
       conjuntos; rela\c c\~oes e fun\c c\~oes; defini\c c\~oes recursivas;
       conceitos b\'asicos de grafos; indu\c c\~ao matem\'atica.
 \item Linguagens Regulares: express\~oes regulares; gram\'aticas regulares;
       aut\^omatos finitos; propriedades.
 \item Linguagens Livres do Contexto: gram\'aticas livres do contexto;
       aut\^omatos a pilha; propriedades.
 \item Linguagens Sens\'{\i}veis ao Contexto: gram\'aticas sens\'{\i}veis ao contexto;
       aut\^omatos lineares limitados; propriedades.
 \item Linguagens Recursivamente Enumer\'aveis: gram\'aticas irrestritas;
       m\'aquinas de Turing; linguagens recursivas; propriedades.
 \item Decidibilidade: problemas de decis\~ao; tese de Church-Turing; o problema
       da parada; m\'aquina de Turing universal; redutibilidade; exemplos de
       problemas indecid\'{\i}veis.
\end{itemize}
 
\section{Bibliografia}
 
Livro texto: 
\begin{itemize}
 \item Sudkamp, T.A. {\it Languages and Machines: An Introduction to the
       Theory of Computer Science\/}, Addison-Wesley, 1988.
\end{itemize}
 
Bibliografia adicional
\begin{itemize}
 \item Aho, A.V., Ullman, J.D. {\it The Theory of Parsing, Translation and
 Compiling\/}, vol I: {\it Parsing\/}, Prentice-Hall, 1972.
 \item Denning, P.J., Dennis, J.B., Qualitz, J.E. {\it Machines, Languages and
 Computation\/}, Prentice-Hall, 1978.
 \item Hopcroft, J.E., Ullman, J.D. {\it Formal Languages and Their Relation
 to Automata\/}, Addison-Wesley, 1969.
 \item Hopcroft, J.E., Ullman, J.D. {\it Introduction to Automata Theory,
 Languages and Computation\/}, Addison-Wesley, 1979.
 \item Lewis, H.R., Papadimitriou, C.H. {\it Elements of the Theory of
 Computation\/}, Prentice-Hall, 1981.
\end{itemize}

\end{document}
\endinput
\end
 

\end{document}
\endinput
\end
 
