\documentclass[11pt,a4paper]{article}

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

\newcounter{conta}
\newcounter{conta2}
\hyphenation{pro-ble-mas}
\begin{document}
 
\noindent Pós-Graduação em Ciência da Computação
 \hfill DCC/ICEx/UFMG \\
{\it Teoria de Linguagens}
 \hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2013 \\
Professor: Newton José Vieira  \hfill    www.dcc.ufmg.br/\verb+~+nvieira; sala 4023/ICEx

\noindent {\bf Plano de Curso}

\vspace*{3mm}
\section{Ementa}
 
Classificação e propriedades das gramáticas, autômatos e linguagens
formais. Decidibilidade.
 
\section{Programa}

\begin{list}{\arabic{conta}}{\usecounter{conta}}
 \item Conceitos Básicos de Matemática: representação; prova de teoremas; conjuntos;
       relações; funções; conjuntos enumeráveis; definições recursivas;
       indução matemática; grafos; linguagens formais; gramáticas; problemas de decisão.
 \item Linguagens Formais
 \begin{list}{\arabic{conta}.\arabic{conta2}}{\usecounter{conta2}}
  \item Linguagens regulares: expressões regulares; gramáticas regulares;
        autômatos finitos; propriedades.
  \item Linguagens livres do contexto: gramáticas livres do contexto;
        autômatos de pilha; propriedades.
  \item Linguagens sensíveis ao contexto: gramáticas sensíveis ao contexto;
        autômatos lineares limitados; propriedades.
  \item Linguagens recursivamente enumeráveis: gramáticas irrestritas;
        máquinas de Turing; linguagens recursivas; propriedades.
 \end{list}
 \item Decidibilidade:  problemas de decisão; tese de Church-Turing;
        o problema da parada; máquina de Turing universal; redutibilidade;
        exemplos de problemas indecidíveis.
\end{list}
 
\section{Texto}

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


\section{Bibliografia Adicional}

Algumas referências que tratam do item 1 do programa, referente ao conteúdo de matemática
discreta necessário 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ção pela McGraw-Hill, de 2009, com o título
       \textit{Matemática Discreta e Suas Aplicações}.)
 \item Velleman, D.J. {\em How To Prove It\/}, Cambridge University Press, 1994.
\end{enumerate}
Caso o aluno não domine algum tópico mencionado no item 1, com exceção de
linguagens formais, gramáticas e problemas de decisão, ele deverá
estudá-lo por conta própria, pois não haverá 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, sendo que a maior parte deles pode ser consultada na biblioteca do ICEx. Os livros mais avançados ou que demandem uma maior maturidade matemática estão 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ômatos\/}, $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ção pela Thomson, de 2007, com o título
       \textit{Introdução \`a Teoria da Computação}.)
 \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ção}
 
A avaliação será feita com base em 3 provas. Antecedendo cada prova será distribuída uma lista de exercícios com nível de dificuldade similar ao da prova. Na aula anterior a cada prova haverá uma aula de resolução de dúvidas.

%O seminário deverá ser apresentado no final do curso. O aluno deverá escolher um tema, de preferência dentro de sua área de atuação, que utilize ou que estenda alguma abordagem ou t\'ecnica vista no curso. Alguns tópicos serão sugeridos durante o curso. Deverá ser entregue uma monografia de 10 a 20 páginas at\'e o dia 17/11/2010 e ser feita uma apresentação em data a ser definida (provavelmente no dia 01/12). Serão considerados para avaliação da monografia: português e simbologia matemática, organização, correção, clareza e completeza. A penalidade para cada dia de atraso na entrega da monografia será de 2 pontos por dia.

Os assuntos e valores de cada item de avaliação são:
\begin{enumerate}
 \item Prova 1: até seção 2.6, 33 pontos.
 \item Prova 2: até seção 4.1, 33 pontos
 \item Prova 3: até capítulo 5, 34 pontos.
% \item Seminário: escolha do aluno, sujeita a aprovação do professor, 20 pontos.
\end{enumerate}
Para cada prova, será assumido que o aluno domina o assunto relativo aos capítulos anteriores aos marcados para a prova. Assim, na formulação das questões poderão ser utilizados conceitos e terminologias de assuntos cobertos em provas anteriores.

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

Este Plano de Curso e outras informações (como soluções de exercícios e provas de semestres anteriores), estarão disponiveis na página http://www.dcc.ufmg.br/\verb+~+nvieira, na entrada relativa \`a disciplina.

%Em hipótese alguma um aluno receberá tratamento especial, seja por ignorar as informações veiculadas durante o curso, seja por se envolver em ocupações que o impeçam de cumprir qualquer atividade.

\end{document}
