Teoria da Computação/Linguagens formais (COS700/MAB 703) - 2022/1

Programa de Engenharia de Sistemas e Computação

Até o início do mês de maio, as aulas serão ministradas de forma remota pelo Google Meet

A partir de maio, as aulas serão presenciais

Professores:

Celina Miraglia Herrera de Figueiredo

Fábio Botler

Monitoria:

Alessandra - abarbozaqueiroz@gmail.com

Rodrigo - rpalmeira1999@poli.ufrj.br

Grupo de WhatsApp

Ementa:

Linguagens Regulares e Autômatos Finitos Determinísticos; Expressões Regulares; Relação entre AFD's e Expressões Regulares; Autômatos Finitos Não-Determinísticos; Operações com Autômatos Finitos e Linguagens Regulares; Lema do Bombeamento para Linguagens Regulares; Gramáticas Regulares; Linguagens Livres de Contexto e Gramáticas Livres de Contexto; Árvores de Análise Sintática; Lema do Bombeamento para Linguagens Livres de Contexto; Autômatos de Pilha; Relação entre Gramáticas Livres de Contexto e Autômatos de Pilha; Máquina de Turing; Introdução à Teoria da Complexidade.

Horário e local das aulas:

Início: 22/03/2022
3a. e 5a., 13-15h
Sala Google Meet

Listas

Lista 1: Entregar até 06/04/2022
Lista 2: Entregar até 22/04/2022
Lista 3: Entregar até 24/05/2022
Lista 4: Entregar até 03/06/2022

Provas

Prova 1: Enviar para Celina até 04/05/2022 - Gabarito
Prova 2: Enviar para Fábio até 18/06/2022

Programação esperada:

Março
22 24	Apresentação do curso, Introdução, Complexidade, Computabilidade, Automatos, Exemplos, Operações regulares, fecho por união
29	Aula especial do professor Hugo Nobrega - slides
31	Não determinismo, conversão determinismo, Construção de subconjuntos, fecho por concatenação, estrela
Abril
5	Não determinismo, conversão determinismo, Construção de subconjuntos, fecho por concatenação, estrela
7 12	Expressões regulares, Expressão regular implica Automato, Bombeamento Linguagem Regular
14	Semana Santa
19	Algoritmo de Brzozowski (substituição), Lema de Arden
21	Tiradentes
26	Gramatica Regular, equivalencia com Automato
26/04-04/05	P1
Maio
5	Linguagens Livre de Contexto Fechamento LCC
10	Árvores de Análise Sintática, Gramáticas ambíguas
12	Bombeamento LLC
17	Automato de pilha
19	Equivalencia AP LLC
24	Máquina de Turing
26	decisor, aceitador, Hierarquia de Chomsky
31	multiplas fitas, não determinismo, fechamento, Tese de Curch-Turing Máquina de Turing universal,
Junho
2	indecidibilidade, problema da Parada
7	Complexidade
10-17	P2

Bibliografia

COUTINHO, S. C.; SCHECHTER, Luis Menasché. Autômatos, Linguagens Formais e Computabilidade..

SIPSER, M. Introdução à Teoria da Computação, 2ª edição. Cengage Learning, ISBN, p. 978-85, 2007.

Extra

M. Sambinelli - Como uma Máquina de Turing pode simular um computador

Luis Menasché - Alan Turing