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

Programa de Engenharia de Sistemas e Computação

Professores:

Celina Miraglia Herrera de Figueiredo

Fábio Botler

Monitoria:

Matheus Cunha Simoes - simoesmc@cos.ufrj.br

Rui Aldé Lopes - aldelopesrui@gmail.com

Guilherme Adamatti Bridi - gabridi@cos.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: 20/03/2023
2a. e 4a., 13-15h
Sala: H-304B

Listas

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

Provas

Prova 1: Enviar para Celina até 02/05/2023 -
Prova 2: Enviar para Fábio até 11/06/2023

Formulário de Avaliação do curso

Programação esperada:

Março
20 22	Apresentação do curso, Introdução, Complexidade, Computabilidade, Automatos, Exemplos, Operações regulares, fecho por união
27	Não determinismo, conversão determinismo
29	Não haverá aula
Abril
3	Não haverá aula
5	Não houve aula devido ao incêndio no bloco H
10	Não haverá aula
12	Construção de subconjuntos, fecho por concatenação, estrela
17 19	Expressões regulares, Expressão regular implica Automato, Bombeamento Linguagem Regular
24	Algoritmo de Brzozowski (substituição), Lema de Arden
26	Gramatica Regular, equivalencia com Automato
27/04-02/05	P1
Maio
1	Dia do trabalho
3	Linguagens Livre de Contexto Fechamento LCC
8	Não haverá aula
10	Árvores de Análise Sintática, Gramáticas ambíguas
15	Bombeamento LLC
17	Automato de pilha
22	Equivalencia AP LLC
24	Máquina de Turing, decisor, aceitador, Hierarquia de Chomsky
29	multiplas fitas, não determinismo, fechamento, Tese de Curch-Turing Máquina de Turing universal,
31	indecidibilidade, problema da Parada
Junho
30/05-11/06	P2
07/06	Aula especial do professor Hugo Nobrega História da Teoria da Computação

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