\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{1}^{\mbox{\underline{o}}}$ semestre de 2018 \\
Professor: Newton José Vieira  \hfill    www.dcc.ufmg.br/\verb+~+nvieira; sala 7328/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 Preliminares: representação; 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},
       2a. edição, 2017.
\end{itemize}
O livro será fornecido capítulo a capítulo no fomato pdf na página da disciplina. De forma alternativa ou complementar, o aluno poderá utilizar alguns dos livros referenciados a seguir.


\section{Bibliografia Adicional}

Algumas referências que tratam do assunto sintetizado no Apêndice A do livro, 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\/},
       5th ed., Pearson, 2003.
 \item Rosen, K.H. {\em Discrete Mathematics and Its Applications\/},
       7th ed., McGraw-Hill, 2011. (Existe tradução pela McGraw-Hill da 6a ed., de 2009, com o
			 título \textit{Matemática Discreta e Suas Aplicações}.)
 \item Velleman, D.J. {\em How To Prove It\/}, 2nd ed., Cambridge University Press, 2006.
\end{enumerate}
Caso o aluno não domine algum tópico mencionado no Apêndice, 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ém outras abordagens, sendo que a maior parte deles pode ser consultada na biblioteca do ICEx.

\begin{enumerate}
 \item Greenlaw, R., Hoover, H.J. {\it Fundamentals of the Theory of Computation\/},
       Morgan Kauffmann, 1998.
 \item Hopcroft, J.E., Motwani, R., Ullman, J.D. {\it Introduction to Automata Theory,
       Languages and Computation\/}, 3rd ed., Addison-Wesley, 2006. (Existe tradução pela
			 Campus da 1a ed., de 2001, com o título \textit{Introdução à Teoria dos Autômatos,
			 Linguagens e Computação}.)
 \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\/}, 2nd ed.,
       Prentice-Hall, 2007.
 \item Linz, P., {\it An Introduction to Formal Languages and Automata\/}, 5th ed.,
       Jones and Bartlett, 2011.
 \item Martin, J.C. {\it Introduction to Languages and the Theory of Computation\/}, 4th ed.,
       McGraw-Hill, 2010.
 \item Menezes, P.B. {\it Linguagens Formais e Autômatos\/}, $6^{\mbox{\underline{a}}}$
       ed., Bookman, 2010.
 \item Moret, B.M. {\it The Theory of Computation\/}, Addison-Wesley, 1998.
 \item R\`ev\`esz, G.E. {\it Introduction to Formal Languages\/}, Dover, 2012.
 \item Sipser, M., {\it Introduction to Theory of Computation}, 3rd ed., Course Technology,
       2012. (Existe tradução pela Thomson da 2a ed., de 2007, com o título \textit{Introdução
			 à Teoria da Computação}.)
 \item Sudkamp, T.A. {\it Languages and Machines: An Introduction to the
       Theory of Computer Science\/}, 3rd ed., Pearson, 2005.
 \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 listas de exercícios, valendo 10 pontos cada uma, e 3 provas, valendo a primeira 24 pontos e as duas outras 23 pontos cada uma. Cada lista de exercícios terá um nível de dificuldade similar ao da prova que virá em seguida. 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 à 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}
