\documentstyle[12pt]{article}
 
\newcounter{conta}
\newcounter{conta2}
\hyphenation{pro-ble-mas}
\begin{document}
 
\noindent P\'os-Gradua\c{c}\~ao em Ci\^{e}ncia da Computa\c{c}\~{a}o
 \hfill DCC/ICEx/UFMG
 
\noindent {\it Teoria de Linguagens}
 \hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2000
 
\noindent Professor: \parbox[t]{14cm}{Newton Jos\'{e} Vieira \\
                     e-mail: nvieira@dcc.ufmg.br; sala 4023/ICEx}

\noindent {\bf Plano de Curso}

\vspace*{3mm}
\section{Ementa}
 
Classifica\c{c}\~ao e propriedades das gram\'aticas, aut\^omatos e linguagens
formais. Decidibilidade. Computabilidade.
 
\section{Programa}
 
\begin{list}{\arabic{conta}}{\usecounter{conta}}
 \item Conceitos B\'asicos de Matem\'atica: representa\c c\~ao; prova de teoremas; conjuntos;
       rela\c c\~oes; fun\c c\~oes; conjuntos enumer\'aveis; defini\c c\~oes recursivas;
       indu\c c\~ao matem\'atica; grafos; linguagens formais; gram\'aticas; problemas de decis\~ao.
 \item Linguagens Formais
 \begin{list}{\arabic{conta}.\arabic{conta2}}{\usecounter{conta2}}
  \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.
 \end{list}
 \item Decidibilidade e Computabilidade: 
 \begin{list}{\arabic{conta}.\arabic{conta2}}{\usecounter{conta2}}
  \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.
  \item Computa\c c\~ao num\'erica: computa\c c\~ao de fun\c c\~oes;
        com\-pu\-ta\-\c c\~ao nu\-m\'e\-ri\-ca; composi\c c\~ao de fun\c c\~oes;
        fun\c c\~oes n\~ao comput\'aveis.
 \end{list}
\end{list}
 
\section{Texto}

Na p\'agina http://www.dcc.ufmg.br/\verb+~+nvieira, na entrada [2000/2] referente \`a disciplina
{\em Teoria de Linguagens\/}, ser\'a
colocada dispon\'{\i}vel uma apostila, na medida em que os cap\'{\i}tulos forem ficando prontos.

 \section{Bibliografia Adicional}

A seguinte lista de livros complementa a apostila e cont\'em outras abordagens para os assuntos
constantes do programa. Os livros mais avan\c cados ou que
demandem uma maior maturidade matem\'atica est\~ao marcados com asteriscos.

\begin{enumerate}
 \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 Floyd. R.M., Beigel, R. {\it The Language of Machines: An introduction to
       computability and formal languages\/}, Computer Science Press, 1994.
 \item Greenlaw, R., Hoover, H.J. {\it Fundamentals of the Theory of Computation\/},
       Morgan Kauffmann, 1998.
 \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 *Howie, J.M. {\it Automata and Languages\/}, Oxford University Press, 1991.
 \item Kelley, D. {\it Automata and Formal Languages: an introduction\/},
       Prentice-Hall, 1995.
 \item *Kozen, D.C. {\it Automata and Computability\/}, Springer, 1997.
 \item Lewis, H.R., Papadimitriou, C.H. {\it Elements of the Theory of
       Computation\/}, Prentice-Hall, 1981.
 \item Martin, J.C. {\it Introduction to Languages and the Theory of
       Computation\/}, McGraw-Hill, 1991.
 \item Menezes, P.B. {\it Linguagens Formais e Aut\^omatos\/}, $2^{\mbox{\underline{a}}}$
       ed., Sagra Luzzatto, 1998.
 \item *Moret, B.M. {\it The Theory of Computation\/}, Addison-Wesley, 1998.
 \item R\`ev\`esz, G.E. {\it Introduction to Formal Languages\/}, Dover, 1983.
 \item Sipser, M., {\it Introduction to Theory of Computation}, PWS Publishing
       Co., 1997.
 \item Sudkamp, T.A. {\it Languages and Machines: An Introduction to the
       Theory of Computer Science\/}, 2nd ed., Addison-Wesley, 1997.
 \item Taylor, R.G., {\it Models of Computation and Formal Languages\/}, Oxford University
       Press, 1998.
 \item Wood, D., {\it Theory of Computation}, John Wiley \& Sons, 1987.
\end{enumerate}
 
\section{Avalia\c{c}\~ao}
 
A avalia\c{c}\~ao ser\'a feita com base em 4 listas de exerc\'{\i}cios, valendo 10 pontos cada uma,
e 4 provas valendo 15 pontos cada uma. A $i$-\'esima lista de e\-xer\-c\'{\i}\-cios, cujo objetivo \'e servir
para o aluno se preparar para a $i$-\'esima prova,  dever\'a ser entregue na aula anterior \`a
$i$-\'esima prova. Nesta aula, cada lista ser\'a corrigida pelo pr\'oprio aluno, com base em resolu\c c\~ao
a ser apresentada pelo professor.

Para a resolu\c c\~ao das listas de exerc\'{\i}cios, cada aluno pode discutir com os colegas e/ou
professor e/ou consultar livros e solu\c c\~oes de exerc\'{\i}cios e provas de semestres anteriores.
Caso voc\^e baseie a solu\c c\~ao de um exerc\'{\i}cio na solu\c c\~ao de um colega ou professor, etc.,
fa\c ca a refer\^encia pertinente. Vamos dar os cr\'editos a quem de direito!
 
As listas de exerc\'{\i}cios, assim como este Plano de Curso e outras informa\c c\~oes (como
solu\c c\~oes de exerc\'{\i}cios e provas de semestres anteriores), estar\~ao disponiveis na p\'agina
http://www.dcc.ufmg.br/\verb+~+nvieira, na entrada relativa \`a disciplina.

\end{document}

\section{Cronograma das Aulas}

\begin{tabular}{rcl}
 \multicolumn{1}{c}{\it Aula} & {\it Data} & \multicolumn{1}{c}{\it Assunto} \\
 01-02 & 08/08 & Apresenta\c{c}\~{a}o do plano de curso \\
 03-04 & 10/08 & 0.1, 0.2, 0.3, 0.4 \\
 05-06 & 17/08 & 0.5, 0.6, 0.7, 0.8 \\
 07-08 & 22/08 & 0.9, 0.10, 0.11, 0.12 \\
 09-10 & 24/08 & 1.1 \\
 11-12 & 29/08 & 1.2.1, 1.2.2\\
 13-14 & 31/08 & 1.2.3 \\
 15-16 & 05/09 & Corre\c c\~{a}o da primeira lista de exerc\'{\i}cios\\ \cline{2-3}
 17-18 & \multicolumn{1}{|c}{12/09} & \multicolumn{1}{l|}{Primeira prova}
  \\ \cline{2-3}
 19-20 & 14/09 & 1.3.1, 1.3.2\\
 21-22 & 19/09 & 1.3.3    \\
 23-24 & 21/09 & 1.4.1, 1.4.2 \\
 25-26 & 26/09 & 1.5 \\
 27-28 & 26/09 & 2.1, 2.2 \\
 29-30 & 28/09 & 2.3, 3.1 \\
 31-32 & 05/10 & Corre\c c\~{a}o da segunda lista de exerc\'{\i}cios\\ \cline{2-3}
 33-34 & \multicolumn{1}{|c}{10/10} & \multicolumn{1}{l|}{Segunda prova}
  \\ \cline{2-3}
 35-36 & 17/10 & 3.1, 3.2 \\
 37-38 & 19/10 & 3.3 \\
 39-40 & 22/10 & 3.4.1, 3.4.2 \\
 41-42 & 24/10 & 3.4.3 \\
 43-44 & 29/10 & 3.4.4 \\
 45-46 & 31/10 & 3.5 \\
 47-48 & 07/11 & Corre\c c\~{a}o  da terceira lista de exerc\'{\i}cios\\ \cline{2-3}
 49-50 & \multicolumn{1}{|c}{09/11} & \multicolumn{1}{l|}{Terceira prova}
  \\ \cline{2-3}
 51-52 & 14/11 & 4.1, 4.2 \\
 53-54 & 16/11 & 4.3, 4.4 \\
 55-56 & 21/11 & 4.5, 4.6 \\
 57-58 & 23/11 & 5.1 \\
 59-60 & 28/11 & 5.2, 5.3 \\
 59-60 & 30/11 & 5.4, 5.5 \\
 61-62 & 05/12 & Corre\c c\~{a}o  da quarta lista de exerc\'{\i}cios \\ \cline{2-3}
 63-64 & \multicolumn{1}{|c}{07/12} & \multicolumn{1}{l|}{Quarta prova}
  \\ \cline{2-3}
\end{tabular}
 
\end{document}
