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

Últimas Notícias

Segundo dia SECCIM 2023

Hoje ocorreu mais um dia da SECCIM, envolvendo até e escrita criativa para uma jornada de aprendizado e inspiração. O leia mais

31/10/2023

Primeiro dia de SECCIM 2023

Primeiro dia de SECCIM 2023

30/10/2023

Descubra Programação da Seccim – Edição 2023!

Na próxima semana se inicia a 12º Semana Acadêmica de Ciência da Computação da UFRRJ (Seccim). A programação promete enriquecer leia mais

27/10/2023


Nota de pesar

É com grande consternação que o Curso e o Departamento de Ciência da Computação comunica à comunidade universitária ruralina o leia mais

19/10/2023

Apresentação do projeto “O Uso do Pensamento Computacional para evitar a retenção e evasão nos cursos de graduação” na SNCT 2023

Nesta quarta-feira, dia 18 de outubro, os alunos Jorge Duarte Miguel Junior, Luiz Filipe Brandi e Maxwel Batalha, junto com leia mais

19/10/2023

mais notícias

Skip to content