ementas

Ementa de Linguagens Formais
Prof. Luis Menasch´ Schechter e Unidade 0: Conceitos B´sicos a 1. Introdu¸˜o ` Teoria de Autˆmatos, Teoria da Computabilidade ca a o e Teoria da Complexidade
2. Alfabetos e Linguagens
3. Opera¸˜es sobre Linguagens: Uni˜o, Interse¸˜o, Diferen¸a, Comco a ca c plemento, Concatena¸˜o e Estrela ca 4. Geradores de Linguagens e Reconhecedores de Linguagens
Unidade 1: Linguagens Regulares
1. Linguagens Regulares (LR’s) e Express˜es Regulares (ER’s) o 2. Autˆmatos Finitos Determin´ o ısticos (AFD’s)
3. Autˆmatos Finitos N˜o Determin´ o a ısticos (AFND’s)
4. Equivalˆncia entre ER’s, AFD’s e AFND’s e 5. Propriedades de Fechamento das Linguagens Regulares
6. Linguagens N˜o Regulares: Lema do Bombeamento para Linguaa gens Regulares
7. Gram´ticas Regulares (GR’s) a 8. Equivalˆncia entre GR’s e AF’s e Unidade 2: Linguagens Livres de Contexto
1. Linguagens Livres de Contexto (LLC’s) e Gram´ticas Livres de a Contexto (GLC’s)
´
2. Arvores de An´lise Sint´tica a a
3. Ambiguidade
4. Propriedades de Fechamento das Linguagens Livres de Contexto
5. Linguagens que n˜o s˜o Livres de Contexto: Lema do Bombeaa a mento para Linguagens Livres de Contexto
6. Autˆmatos de Pilha N˜o Determin´ o a ısticos (AP’s)
7. Equivalˆncia entre GLC’s e AP’s e Unidade 3: Um Modelo Formal de Computa¸˜o: As M´quinas de Turing ca a
1. M´quina de Turing a 2. Computa¸˜es com M´quinas de Turing co a
1

3. Linguagens Recursivas
4. Linguagens Recursivamente Enumer´veis a 5. M´quinas de Turing de M´ltiplas Fitas a u
6. M´quinas de Turing N˜o Determin´ a a ısticas 7. Propriedades de Fechamento das Linguagens Recursivas e Recursivamente Enumer´veis a 8. Tese de Church-Turing
9. M´quina de Turing Universal a 10. Problema da Parada
Unidade 4: Teoria da Complexidade
1. Problemas Trat´veis e Intrat´veis a a
2. Classes de Complexidade
3. Defini¸˜es das classes P , N P , co-N P , P SP ACE, N P SP ACE, co EXP T