Informações que irão auxiliá-lo a cursar bem a disciplina e a compreender sua importância para o curso.

Ementa

• Teorias dos autômatos e das linguagens formais
• Modelos computacionais: autômato finito e autômato de pilha
• Linguagens regulares e linguagens livre-de-contexto
• Propriedades e problemas
• Parsing e ambiguidade em linguagens livre-de-contexto
• Hierarquia de autômatos, de gramáticas e de linguagens
• Teoria da computabilidade.
• Limitações dos autômatos
• Máquina de Turing como modelo de algoritmo
• Tese de Church-Turing, justificativa e consequências
• Máquinas de Turing como reconhecedoras de linguagens e como calculadoras de funções
• Problemas de decisão em linguagens regulares e livre-de-contexto
• A indecidibilidade do problema da parada
• Redução

Visão Geral

Ainda não temos uma visão geral dessa disciplina. Você pode nos ajudar com isso? (:

Dicas

• O assunto da matéria é totalmente cumulativo, do início ao fim. Sendo assim, é importante manter uma sequência constante nos estudos com o intuito de não acumular conteúdos.
• Por se tratar de uma matéria teórica, é interessante o uso de alguma ferramenta para auxiliar a visualização dos conceitos vistos em aula. O JFLAP é recomendado.
• Faça os exercícios de fixação (que não valem nota). Com eles você vai conseguir levar dúvidas para as aulas e conseguir resolver os exercícios avaliativos mais facilmente.