LFA

Aqui serão colocados os materiais para a disciplina de Linguagens Formais e Autômatos – LFA

Plano da Disciplina

 

Aulas 😉

• Aula 00 – Intro
• Aula 01 – Conceitos Básicos
• Aula 02 – Autômatos e Linguagem Regular
• Aula 03 – Autômatos Finitos Não Determinísticos
• Aula 04 – Autômatos Finitos com Movimento Vazio
  • Conversão AFNe -> AFN -> AFD: Notas de Aula AFNe
• Aula 05 – Expressão Regular e Gramática Regular
• Aula 06 – paulo-blauth-menezes-linguagens-regulares – Gramática Regular
• Aula 07 – Lema do Bombeamento…
• Aula 08 – Minimização de Autômatos
• Aula 09 – Autômato Finito com Saída

Parte 2

• Aula 10 – Linguagens Livres do Contexto
• Aula 11 – Simplificação de Gramáticas Livres do Contexto
• Aula 12 – Formas Normais
• Aula 13 – Autômato com Pilha
• Aula 14 – Autômato com Pilha e Linguagens Livre do Contexto
  • AP a partir de uma GLC na forma normal de Greibach
• Aula 15 – Algoritmos de Reconhecimento (AP a partir de uma GLC e CYK)
• Aula 16 – Algoritmo de Early
• Aula 17 – Linguagens Enumeráveis Recursivamente e Sensíveis ao Contexto
• Aula 18 – Máquinas de Turing como Reconhecedores

Exercícios

• Lista 1: listaex01v2
  • Opcional: exeropcional
• Lista 2:
  • Fazer os ex. 3.1, 3.2, 3.3, 3.5, 3.6,3.11, 3.12 e 3.19 desta lista: Ex Gramatica AP – Menezes
  • Pode substituir os ex 3.1, metade do 3.2, metade do 3.3, 3.11 e 3.12 por alguns destes: ExercicioAlternativo2
• Pontuação extra 😀
  • Desafio: Implementar AFN/AFNe (ver com monitor)
  • Descrever e apresentar um exemplo do Algoritmo de Greibach
  • Descrever e apresentar um exemplo do Algoritmo de Eliminação de Recursão a Esquerda

Trabalho Final

• Descrição Trabalho Final
  • Exemplo usando Flex (reconhecedor léxico): src
    • teste.pas está compactado nesse exemplo src.