Linguagens Formais e Autômatos – TIN0119

Objetivos da Disciplina

Capacitar o aluno a:

• Identificar e classificar linguagens geradas por gramáticas
• Escrever gramáticas que representem linguagens
• Projetar máquinas que manipulem a linguagem
• Identificar o potencial e o limite de diferentes tipos de máquinas teóricas para manipulação de linguagens
• Projetar linguagens e máquinas capaz de resolverem problemas reais
• Verificar se um problema pertence ou não a classe de problemas intratáveis

Ementa

Hierarquia de Chomsky. Alfabetos e linguagens. Gramáticas. Autômatos finitos e linguagens regulares; máquinas de pilha e linguagens livres de contexto, gramáticas LL(k) e LR(k); gramáticas sensíveis a contexto. Máquinas de Turing. Capacidade e limite de cada classe. Decidibilidade e Computabilidade.

Conteúdo Programático

• Revisão de conceitos de conjuntos, funções e relações
• Apresentação dos conceitos de alfabetos, cadeias e linguagens
• Definição dos conceitos de procedimentos e algoritmos, conjuntos recursivos e recursivamente enumeráveis
• Gramáticas: definição e tipos de gramáticas
• Linguagens e gramáticas regulares
  • Autômatos finitos: determinísticos e não-determinísticos
  • Equivalência
  • Minimização de autômatos
  • Expressões regulares
  • Equivalência entre autômatos finitos e gramáticas regulares
• Linguagens e gramáticas livres de contexto
  • Linguagens livres de contexto
  • Autômatos de pilha
• Máquinas de Turing
• Decidibilidade e computabilidade
• Linguagens sensíveis a contexto e autômatos linearmente limitados
• Linguagens determinísticas e seus aceitadores

Metodologia

Exposição de conteúdo: aulas presenciais terão apresentação do conteúdo teórico e aplicação dos exercícios de fixação.
Aprendizagem colaborativa: para o entendimento dos conteúdos serão apresentados questões, pelo professor, cujas soluções serão propostas e discutidas pelos alunos.
Aprendizagem baseada em projeto: a partir dos exemplos de sistemas apresentados em sala, o aluno deverá desenvolver um projeto para a solução de um problema prático ou apresentado na literatura.

Avaliação

Avaliação contínua: Ao longo da disciplina, o estudante entregará tarefas intermediárias aplicando e fixando individualmente o conteúdo da disciplina em exercícios propostos pelo professor. Em grupos, os estudantes respondem à cada aula a um conjunto de questões propostas pelo professor.
Avaliação Somativa: Ao longo da disciplina haverão três avaliações(G1, G2 e G3) para o cálculo da nota final.
Avaliação 1 (G1): Esta será composta de um prova teórica versando sobre os conceitos ministrados, trabalhos individuais e as participações em sala de aula.
Avaliação 2 (G2): Esta será composta de um prova teórica versando sobre os conceitos ministrados, participações em sala de aula e um projeto para aplicar os conceitos teóricos apresentados na solução de um problema real ou apresentado pela literatura.

Se média das duas avaliações do aluno for maior ou igual a 7,0 será aprovado sem necessidade de prova final (G3). Caso contrário, fará uma prova final.

Cálculo da nota-final: A nota final será igual a média da G1e a G2 se esta for maior que 7,0 senão esta será igual a ((média da G1 e a G2) + G3)/2.

Serão aprovados apenas os alunos com média final igual ou superior a 5,0.

Bibliografia

• HOPCROFT ,J. E.; ULLMAN , J. D., e MONTWANI , R. ; Introdução à Teoria de Autômatos Linguagens e Computação. Editora Campus, tradução da segunda edição americana, 2002.
• MENEZES , P. B.; Linguagens Formais e Autômatos. Editora Sagra Luzzatto, 2000.
• DIVERIO , T.A.; MENEZES, P.B.; Teoria da Computação: Máquinas Universais e Computabilidade. Editora Sagra Luzzatto, 1999.
• Apostila de Linguagens Formais e Autômatos redigida pelo Prof. José Lucas RANGEL.