A tabela as seguir apresenta todas as disciplinas com vagas disponíveis para os discentes do Curso de ENGENHARIA COMPUTACIONAL (65B) da Universidade Federal de Juiz de Fora (UFJF) no período letivo atual. Os horários e os docentes responsáveis por cada disciplina podem ser consultados clicando na turma desejada.
Ressalta-se que o Curso de Engenharia Computacional da UFJF é ofertado em período integral, com aulas de segunda a sexta-feira, podendo ocorrer nos turnos matutino (8h às 12h), vespertino (14h às 18h) ou noturno (19h às 23h), conforme estabelecido na grade curricular.
Plano de Ensino
Disciplina: DCC063 - LINGUAGENS FORMAIS E AUTÔMATOS
Carga horária: 60
Departamento: DEPTO DE CIENCIA DA COMPUTACAO /ICE
Ementa
-Noções preliminares
-Linguagens regulares
-Gramáticas e linguagens livres de contexto
-Formas normais
-Autômatos e linguagens
-Autômatos com pilha e linguagens livres de contexto
-Hierarquia de Chomsky: classes de linguagens
-Linguagens regulares
-Gramáticas e linguagens livres de contexto
-Formas normais
-Autômatos e linguagens
-Autômatos com pilha e linguagens livres de contexto
-Hierarquia de Chomsky: classes de linguagens
Conteúdo
1) Noções preliminares
Teoria de conjuntos. Produto cartesiano, relações entre conjuntos, funções, relações de equivalência. Conjuntos enumeráveis e não enumeráveis. Definições recursivas. Indução matemática e diagonalização. Tipos de formalismos: grafos direcionados e lambda-cálculo.
2) Linguagens regulares
Definição de strings e linguagens. Especificação finita de linguagens. Conjuntos e expressões regulares.
3) Gramáticas e linguagens livres de contexto
Definições de linguagens livres de contexto. Derivação. Gramáticas regulares. Exemplos de gramáticas e linguagens: Pascal e expressões aritméticas. Estratégias de derivação: ambigüidade, derivações mais à esquerda e mais à direita, grafos de gramáticas, derivadores top-down, derivadores bottom-up.
4) Formas normais
Definição de formas normais e esquemas de restrição em gramáticas. Eliminação de: produções lambda, produções em cadeia, símbolos redundantes, recursão à esquerda. Forma normal de Chomsky e de Greibach
5) Autômatos e linguagens
Máquinas de estados finitos. Autômato finito determinista e não-determinista. Remoção de não-determinismo: fecho lambda. Minimização de autômatos finitos deterministas. Autômatos finitos e conjuntos regulares. O lema do bombeamento para linguagens regulares.
6) Autômatos com pilha e linguagens livres de contexto
Definições de autômato com pilha. Autômatos com pilha e linguagens livres de contexto. O lema do bombeamento para linguagens livres de contexto. Autômato com duas pilhas.
7) Hierarquia de Chomsky: classes de linguagens
Propriedades fechadas de linguagens regulares. Propriedades fechadas de linguagens livres de contexto. Tópicos para a próxima disciplina: Teoria de Linguagens.
Teoria de conjuntos. Produto cartesiano, relações entre conjuntos, funções, relações de equivalência. Conjuntos enumeráveis e não enumeráveis. Definições recursivas. Indução matemática e diagonalização. Tipos de formalismos: grafos direcionados e lambda-cálculo.
2) Linguagens regulares
Definição de strings e linguagens. Especificação finita de linguagens. Conjuntos e expressões regulares.
3) Gramáticas e linguagens livres de contexto
Definições de linguagens livres de contexto. Derivação. Gramáticas regulares. Exemplos de gramáticas e linguagens: Pascal e expressões aritméticas. Estratégias de derivação: ambigüidade, derivações mais à esquerda e mais à direita, grafos de gramáticas, derivadores top-down, derivadores bottom-up.
4) Formas normais
Definição de formas normais e esquemas de restrição em gramáticas. Eliminação de: produções lambda, produções em cadeia, símbolos redundantes, recursão à esquerda. Forma normal de Chomsky e de Greibach
5) Autômatos e linguagens
Máquinas de estados finitos. Autômato finito determinista e não-determinista. Remoção de não-determinismo: fecho lambda. Minimização de autômatos finitos deterministas. Autômatos finitos e conjuntos regulares. O lema do bombeamento para linguagens regulares.
6) Autômatos com pilha e linguagens livres de contexto
Definições de autômato com pilha. Autômatos com pilha e linguagens livres de contexto. O lema do bombeamento para linguagens livres de contexto. Autômato com duas pilhas.
7) Hierarquia de Chomsky: classes de linguagens
Propriedades fechadas de linguagens regulares. Propriedades fechadas de linguagens livres de contexto. Tópicos para a próxima disciplina: Teoria de Linguagens.
Bibliografia
HOPCROFT, J. E. Introdução a teoria de autômatos, linguagens e computação. Rio de Janeiro: Elsevier. 560 p
LEWIS, H. R.; PAPADIMITRIOU, C. H. Elementos de teoria da computação. Porto Alegre: Bookman. 2000. 354 p.
SIPSER, M. Introdução à teoria da computação: Thomson Learning. 2007. 488 p.
LEWIS, H. R.; PAPADIMITRIOU, C. H. Elementos de teoria da computação. Porto Alegre: Bookman. 2000. 354 p.
SIPSER, M. Introdução à teoria da computação: Thomson Learning. 2007. 488 p.
Bibliografia(continuação)
Não informado
Bibliografia complementar
AHO, A. V.; LAM, M. S.; SETHI, R. Compiladores: Princípios, técnicas e ferramentas Rio de Janeiro: Pearson. 2007. 648 p.
COOPER, Keith D.; TORCZON, Linda. Construindo Compiladores. 2a Ed. Rio de Janeiro: Elsevier. 2014.
MENEZES, P. B. Linguagens formais e autômatos. Porto Alegre: Sagra Luzzatto. 2000. 170 p.
RAMOS, M. V. M.; NETO, J. J.; VEGA, Í. S. Linguagens formais: Teoria, modelagem e implementação. Porto Alegre: Bookman. 2009. 656 p.
ROSA, João Luis Garcia. Linguagens Formais e Autômatos. Rio de Janeiro: LTC Editora. 2010.
COOPER, Keith D.; TORCZON, Linda. Construindo Compiladores. 2a Ed. Rio de Janeiro: Elsevier. 2014.
MENEZES, P. B. Linguagens formais e autômatos. Porto Alegre: Sagra Luzzatto. 2000. 170 p.
RAMOS, M. V. M.; NETO, J. J.; VEGA, Í. S. Linguagens formais: Teoria, modelagem e implementação. Porto Alegre: Bookman. 2009. 656 p.
ROSA, João Luis Garcia. Linguagens Formais e Autômatos. Rio de Janeiro: LTC Editora. 2010.