Linguagens Formais e Autômatos

Período letivo 2013.1:

• Campus Juazeiro, sala 16
• Segundas, das 8:00 às 10:00 hs
• Quartas, das 8:00 às 10:00 hs
• Programa da disciplina
• PUD

Material didático:

• Linguagens Formais: Teoria, Modelagem e Implementação
  Em co-autoria com os Profs. João José Neto e Ítalo Santiago Vega
  Editora Bookman 2009. ISBN 9788577804535. 656 páginas
• JFLAP - um simulador gráfico e interativo para experimentação com gramáticas, expressões regulares e autômatos:
  • Download (renomeie para "JFLAP.jar" caso o seu S.O. modifique o nome para "JFLAP.zip")
  • Site
• Livro "Foundations of Computer Science" de A.V. Aho e J.D. Ullman, disponível para download gratuito na página dos autores:
  • Capítulo 7 - The Set Data Model
  • Capítulo 10 - Patterns, Automata, and Regular Expressions
  • Capítulo 11 - Recursive Description of Patterns
• 40 exercícios sobre linguagens regulares, com solução.
• Documentário Dangerous Knowledge, de David Malone para a BBC, sobre as vidas e obras de Cantor, Boltzmann, Gödel e Turing.

Slides:

• Elementos de matemática discreta
• Conceitos básicos de linguagens
• Linguagens regulares
• Linguagens livres de contexto
• Linguagens sensíveis ao contexto
• Conclusões

Avaliações:

• Prova 1 (resolução)
• Prova 2 (resolução)
• Prova final (resolução)
• Trabalho

Aulas ministradas:

Aula 01 - 2013-05-27 - Apresentação da disciplina. Motivação e objetivos.

Aula 02 - 2013-05-29 - Conjuntos e relações.

Aula 03 - 2013-06-03 - Funções e conjuntos enumeráveis. Símbolo, alfabeto, cadeia e linguagem formal.

Aula 04 - 2013-06-05 - Operações sobre cadeias e linguagens. Gramáticas e linguagens definidas por gramáticas.

Aula 05 - 2013-06-10 - Exemplos e exercícios.

Aula 06 - 2013-06-12 - Equivalência de gramáticas. Linguagens e conjuntos. Reconhecedores. Gramáticas lineares à direita e à esquerda.

Aula 07 - 2013-06-17 - Gramáticas lineares não-unitárias. Conjuntos regulares. Expressões regulares.

Aula 08 - 2013-06-19 - Exercícios de expressões regulares. Autômatos finitos.

Aula 09 - 2013-06-26 - Exercícios de autômatos finitos. Autômato finito não-determinístico.

Afastamento para doutorado a partir do dia 1º de julho de 2013. As aulas terão continuidade com professor substituto contratado pela universidade.