Clique para ir ao início Universidade de Brasília - UnB
Decanato de Ensino de Graduação - DEG
Secretaria de Administração Acadêmica - SAA
MatrículaWeb
GRADUAÇÃO
  Seja bem-vindo(a).
  Para ter acesso ao menu de Aluno, faça o login.
MatrículaWeb  clique aqui para fazer o login.
 


Período Atual
2017/2


Disciplina - Listagem de Ementa/Programa
Disciplina: 113948 - LINGUAGENS FORMAIS E AUTOMATOS
(Ver Oferta)

Graduação

Curso
Oferta
Telefones
Calendário
Mensagem da SAA
Benefícios DAC


Órgão: MAT - Departamento de Matemática.
Código: 113948
Denominação: LINGUAGENS FORMAIS E AUTOMATOS
Nível: Graduação
Vigência: 1962/1
Pré-req: Disciplina sem pré-requisitos
Ementa:

CONCEITOS BASICOS:

AUTOMATOS FINITOS E EXPRESSOES REGULARES

GRAMATICAS LIVRES DE CONTEXTO

AUTOMATO A PILHA

MAQUINAS DE TURING

Programa:

1. CONCEITOS BASICOS: ALFABETOS, PALAVRAS E LINGUAGENS. GRAFOS E ARVO-

RES. PRINCIPIO DA INDUCAO MATEMATICA.

2. AUTOMATOS FINITOS DETERMINISTICOS E NAO-DETERMINISTICOS.

AUTOMATOS FINITOS COMTRAMSICOES E. ESPRESSOES REGULARES. PROPRIEDA-

DES DOS CONJUNTOS REGULARES. TEOREMA DE MYHILL-NERODE. AUTOMATO

MINIMO.

3. GRAMATICAS LIVRES DE CONTEXTO. ARVORES DE DRIVACAO.

REDUCAO DE GRAMATICAS LIVRES DE CONTEXTO. FORMAS NORMAIS DE CHOMSKY

E GREIBACH. AMBIGUIDADE.

4. AUTOMATOS A PILHA. DETERMINISTICO E NAO-DETERMINISTICO.

EQUIVALENCIA ENTRE AUTOMATO A PILHA E LINGUAGENS LIVRES DE CONTEXTO.

5. MAQUINAS DE TURING. MODIFICACOES DA MAQUINA DE TURING. LINGUAGENS

RECURSIVAMENTE ENUMERAVEIS E SUA EQUIVALENCIA COM LINGUAGENS DO TIPO

PO O. O PROPLEMA DA PARADA DA MAQUINA DE TURING. PROBLEMAS INDECI-

SIVEIS.

Bibliografia:

JOHN E. HOPCROFT NEW YORK

INTRODUCTION TO AUTOMATA THEORY

LANGUAGES AND COMPUTATION ADDISON WESLEY 1979

IMRE SIMON IMECC UNICAMP

LINGUAGENS FORMAIS E AUTOMATOS II ESC.DE COMPUT1981

© 2017 CPD - Centro de Informática
UnB - Universidade de Brasília