Objetivos
Apresenta modelos matemáticos para formalização, especificação e reconhecimento de linguagens computacionais, capacitando para a compreensão e/ou desenvolvimento de software básico incluindo compiladores e linguagens de programação; estuda os principais fundamentos da teoria da computação associados à computabilidade e solucionabilidade de problemas, bem como formalização de programas, máquinas, computação e formalismos que os definem.
Pré-requisitos
Embora os pré-requisitos não sejam obrigatórios, o seu domínio auxiliará muito na evolução do aprendizado:
- Estruturas de dados (Conjuntos, Listas, Grafos e Hashtables)
- Conhecimento intermediário em Python ou C/C++
- Noções básicas de Git e Github
Competências trabalhadas
As competências trabalhadas na disciplina são:
- Tratar problemas computacionais de maneira formal.
- Formalizar e especificar modelos matemáticos capazes de reconhecer linguagens com base nos conceitos teóricos da computação.
- Desenvolver aplicações computacionais tais como compiladores, modelagem de sistemas e linguagens de programação.
- Aprimorar aplicações computacionais já existentes.
Unidades de aprendizagem
- Análise crítica sobre os diversos tipos de autômatos finitos como reconhecedores de linguagens.
- Compreensão sobre os formalismos geradores de palavras para criação de uma linguagem de programação.
- Análise reflexiva das diferentes propriedades das linguagens regulares.
- Estudo e prática de forma colaborativa sobre as gramáticas livres de contexto, árvore de derivação e suas simplificações correlacionando e contextualizando com as fases de um compilador.
- Visão sistêmica sobre as formas normais de Chomsky como ferramenta de padronização de geradores de linguagens.
- Compreensão sobre os formalismos associados às linguagens livres de contexto para o seu reconhecimento com postura analítica.
- Identificação e análise reflexiva acerca das propriedades de fechamento e lema do bombeamento das linguagens livres de contexto.
- Análise crítica para aplicação da Máquina de Turing como reconhecedor de linguagem.
- Realização de simulações e experimentos práticos de linguagens formais, solucionando problemas de forma individual e cooperativa.
Estratégias metodológicas
Elaboração de artigos e trabalhos práticos relacionados às unidades de aprendizagem
Cronograma
| Grau |
Descrição |
Peso na nota final |
| G1 |
Implementação de um programa para simulação de autômatos finitos determinísticos. |
2,0 |
| G1 |
Implementação de um programa para a conversão de autômatos finitos não-determinísticos em autômatos finitos determinísticos. |
2,0 |
| G1 |
Resolução de exercícios de prova matemática para autômatos finitos. |
1,0 |
| G2 |
Elaboração de artigo sobre a definição de uma linguagem de programação utilizando gramáticas livres de contexto. |
2,0 |
| G2 |
Elaboração de artigo e apresentação sobre decidibilidade e a Máquina de Turing. |
2,0 |
| G2 |
Implementação de um simulador de Máquina de Turing. |
1,0 |
Procedimentos e Critérios de Avaliação
A nota final será composta por trabalhos práticos de implementação, e será calculada com a média (M) dada pela regra M = (G1 + G2) / 2, sendo G1 e G2 graus parciais formados totalmente por trabalhos práticos.
Para obter a aprovação, o aluno deve obter uma média (M) igual ou superior a 6, com frequência mínima de 8 encontros presenciais.
Material Complementar
Bibilografia
- Menezes, Paulo Blath. Linguagers Formais e Autômatos. 6a ed. Bookman, 2011.
- Sipser, Michael. Introdução à Teoria da Computação. Tradução da 2a. ed. americana. Cengage Learning, 2005.
- Aho, Lam, Sethi e Ulmann. Compiladores: Princípios, Técnicas e Ferramentas. 2a ed. Pearson Addison Wesley, 2008.