Linguagens Formais e Autômatos (IM854)

Informações

Código: IM854

Pré-requisito

Lógica para a Computação

Ementa

Introdução. Conceitos Centrais da Teoria dos Autômatos. Linguagens Regulares e Autômatos Finitos. Linguagens Livres de Contexto e Autômatos de Pilha. Máquinas de Turing e Linguagens.

Objetivos:

Ao final da disciplina o aluno deve:

(a) Apresentar as linguagens formais, as máquinas reconhecedoras (autômatos) e as gramáticas principais da Hierarquia de Chomsky, mostrando o relacionamento existente entre cada tipo de linguagem, os autômatos que as reconhecem, e as gramáticas que as geram;

(b) Apresentar as máquinas de Turing e as noções de decidibilidade e indecidibilidade;

(c) Discutir os limites da computação convencional.

Conteúdo Programático

Sumário

1. Introdução
2. Conceitos Centrais da Teoria dos Autômatos
3. Linguagens Regulares e Autômatos Finitos
4. Linguagens Livres de Contexto e Autômatos de Pilha
5. Máquinas de Turing e Linguagens

Tópicos de Aula

01. Introdução

• Motivação e apresentação da disciplina

02. Conceitos Centrais da Teoria dos Autômatos

• Alfabeto
• Cadeia (String)
• Operações envolvendo cadeias
• Fechamento de Kleene e fechamento positivo
• Noção formal de linguagem
• Noção formal de gramática, derivação
• Relacionamento entre linguagens, gramáticas e reconhecedores
• Hierarquia de Chomsky

03. Linguagens Regulares e Autômatos Finitos

• Autômatos finitos determinísticos
• Autômatos finitos não*determinísticos
• Equivalência entre autômatos finitos determinísticos e não*determinísticos
• Gramática Regular
• Equivalência entre gramáticas regulares e autômatos finitos
• Operações sobre autômatos: união, concatenação, estrela (star), interseção e complementação
• Expressões regulares
• Expressões regulares e autômatos finitos
• Minimização e equivalência de autômatos
• Lema do Bombeamento para Linguagens Regulares

04. Linguagens Livres de Contexto e Autômatos de Pilha

• Gramáticas Livres de Contexto
• Árvores de Derivação: derivação mais à esquerda e ambiguidade
• Forma Normal de Chomsky
• Autômatos de pilha
• Autômato de pilha determinístico
• Linguagens reconhecidas por pilha vazia e por estado final
• De pilha vazia ao estado final e de estado final para pilha vazia
• Linguagens e autômatos de pilha determinísticos
• Forma Normal de Greibach
• Equivalência entre gramáticas livres de contexto e autômatos de pilha
• Autômatos de pilha e número de estados
• Autômatos de pilha e o poder computacional

05. Máquinas de Turing e Linguagens

• Máquina de Turing como mecanismo reconhecedor de linguagem
• Linguagem reconhecida por uma máquina de Turing
• Linguagem recursiva, recursivamente enumerável e não recursivamente enumerável
• Máquina de Turing como mecanismo de cálculo
• Problemas de Decisão
• Linguagem Turing decidível, Turing reconhecível e não*Turing decidível
• Propriedades
• Modelos equivalentes à Máquina de Turing
• Tese de Church*Turing
• O Problema da Parada

Referencia Bibliográfica

Bibliografia Básica

1. HOPCROFT, John E.; ULLMAN, Jeffrey D; MOTWANI, Rajeev. Introdução à teoria de autômatos, linguagens e computação. Rio de Janeiro: Elsevier, 2003.
2. LEWIS, Harry R; PAPADIMITRIOU, Christos H. Elementos de teoria da computação. 2. ed. rev. Porto Alegre: Bookman, 2000.
3. RAMOS, Marcus Vinícius Midena; JOSÉ NETO, João; VEGA, Ítalo Santiago. Linguagens formais: teoria, modelagem e implementação. Porto Alegre: Bookman, 2009.

Bibliografia Complementar

1. PAPADIMITRIOU, Christos H. Computational complexity. Reading, Mass.: Addison Wesley, 1994.
2. SIPSER, M. Introdução à Teoria da Computação. 2ª.ed. Cengage Learning, 2012.
3. MENEZES, P. B. Linguagens Formais e Autômatos. 6ª. ed., Bookman, 2010.
4. VIEIRA, N. J. Introdução aos Fundamentos da Computação: linguagens e máquinas. Cengage Learning, 2015.
5. SILVA, F. S. C.; MELO, A. C. V. Modelos Clássicos de Computação. Thomson Learning, 2006.

Postado em 18/11/2013 - 07:46 - Atualizado em 15/08/2023 - 15:02