\documentclass[11pt,a4paper]{article}

\usepackage[brazil]{babel}
\usepackage[latin1] {inputenc}
\usepackage{fullpage}

\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 \\
{\it Teoria de Linguagens}
 \hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2010 \\
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.
 
\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 de 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:  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{list}
 
\section{Texto}

O programa ser\'a desenvolvido com base no livro-texto:
\begin{itemize}
 \item Vieira, N.J. {\em Introdu\c c\~ao aos Fundamentos da Computa\c c\~ao:
       Linguagens e M\'aquinas},
       Pioneira Thomson Learning, 2006.
\end{itemize}
De forma alternativa ou complementar, o aluno poder\'a utilizar alguns dos livros referenciados a seguir.


\section{Bibliografia Adicional}

Algumas refer\^encias que tratam do item 1 do programa, referente ao conte\'udo de matem\'atica
discreta necess\'ario para um bom acompanhamento do curso:
\begin{enumerate}
 \item Dean, N. {\em The Essence of Discrete Mathematics\/}, Prentice Hall, 1997.
 \item Grimaldi, R.P. {\em Discrete and Combinatorial Mathematics: An Applied Introduction\/},
       3rd ed., Addison-Wesley, 1994.
 \item Rosen, K.H. {\em Discrete Mathematics and Its Applications\/},
       6th ed., McGraw-Hill, 2007. (Existe tradu\c{c}\~ao pela McGraw-Hill, de 2009, com o t\'{\i}tulo
       \textit{Matem\'atica Discreta e Suas Aplica\c{c}\~oes}.)
 \item Velleman, D.J. {\em How To Prove It\/}, Cambridge University Press, 1994.
\end{enumerate}
Caso o aluno n\~ao domine algum t\'opico mencionado no item 1, com exce\c{c}\~ao de
linguagens formais, gram\'aticas e problemas de decis\~ao, ele dever\'a
estud\'a-lo por conta pr\'opria, pois n\~ao haver\'a aula sobre o mesmo.

A seguinte lista de livros complementa o livro-texto e cont\'em outras abordagens para os assuntos
constantes dos itens 2 e 3 do programa. Os livros mais avan\c cados ou que
demandem uma maior maturidade matem\'atica est\~ao marcados com asteriscos.

\begin{enumerate}
 \item Cohen, I.A.D. {\it Introduction to Computer Science\/}, rev. ed.,
       Wiley and Sons, 1991.
 \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 Introduction to Automata Theory,
       Languages and Computation\/}, Addison-Wesley, 1979.
 \item Hopcroft, J.E., Motwani, R., Ullman, J.D. {\it Introduction to Automata Theory,
       Languages and Computation\/}, 2nd ed., Addison-Wesley, 2001.
 \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 Lawson, M.V., {\it Finite Automata\/}, Chapman \& Hall/CRC, 2004.
 \item Lewis, H.R., Papadimitriou, C.H. {\it Elements of the Theory of
       Computation\/}, Prentice-Hall, 1981.
 \item Linz, P., {\it An Introduction to Formal Languages and Automata\/}, 2nd ed.,
       Jones and Bartlett, 1997.
 \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 Parkes, A.P. {\it Introduction to Languages, Machines and Logic: Computable
       Languages, Abstract Machines and Formal Logics\/}, Springer, 2002.
 \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. (Existe tradu\c{c}\~ao pela Thomson, de 2007, com o t\'{\i}tulo
       \textit{Introdu\c{c}\~ao \`a Teoria da Computa\c{c}\~ao}.)
 \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 3 provas e 1 semin\'ario.

Antecedendo cada prova ser\'a distribu\'{\i}da uma lista de exerc\'{\i}cios
com n\'{\i}vel de dificuldade similar ao da prova. Na aula anterior a cada prova
haver\'a uma aula de resolu\c{c}\~ao de d\'uvidas.

O semin\'ario dever\'a ser apresentado no final do curso. O aluno
dever\'a escolher um tema, de prefer\^encia dentro de sua \'area de atua\c c\~ao, que utilize ou
que estenda alguma abordagem ou t\'ecnica vista no curso. Alguns t\'opicos ser\~ao sugeridos durante
o curso. Dever\'a ser entregue uma monografia
de 10 a 20 p\'aginas at\'e o dia 18/11/2010 e ser feita uma apresenta\c c\~ao em data a ser definida
(provavelmente no dia 23/11).
Ser\~ao considerados para avalia\c c\~ao da monografia: portugu\^es e simbologia matem\'atica,
organiza\c c\~ao, corre\c c\~ao, clareza e completeza. A penalidade para cada dia de atraso na entrega
da monografia ser\'a de 2 pontos por dia.

Os assuntos e valores de cada item de avalia\c c\~ao s\~ao:
\begin{enumerate}
 \item Prova 1: caps. 1 e  2 (at\'e 2.4), 26 pontos.
 \item Prova 2: caps. 2 (a partir de 2.5) e 3, 27 pontos
 \item Prova 3: caps. 4 e  5, 27 pontos.
 \item Semin\'ario: escolha do aluno, sujeita a aprova\c c\~ao do professor, 20 pontos.
\end{enumerate}
Para cada prova, ser\'a assumido que o aluno domina o assunto relativo aos
cap\'{\i}tulos anteriores aos marcados para a prova. Assim, na formula\c c\~ao
das quest\~oes poder\~ao ser utilizados conceitos e terminologias de
assuntos cobertos em provas anteriores.

Durante as aulas poder\~ao ser propostos outros exerc\'{\i}cios, provas ou
quaisquer outros tipos de atividades valendo pontos extra ou para
substituir itens da avalia\c c\~ao normal. {\bf No entanto, o professor n\~ao
vai se preocupar em divulgar para alunos faltosos quaisquer atividades destas!}

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.

A partir da segunda aula ser\'a assumido que o aluno estar\'a ciente:
\begin{itemize}
 \item de todas informa\c c\~oes contidas neste plano de curso;
 \item de todas as atividades programadas, estejam elas anotadas
       na p\'agina ou n\~ao.
\end{itemize}
Em hip\'otese alguma um aluno receber\'a tratamento especial, seja por ignorar
tais informa\c c\~oes ou atividades, seja por se envolver em ocupa\c c\~oes que o
impe\c cam de cumprir qualquer atividade prevista no curso.

\end{document}
