CT200 - Fundamentals of Automata and Formal Languages

Fundamentos de Autômatos e Linguagens Formais

Objetivo Geral da Disciplina CT-200

Propiciar aos alunos de Pós-Graduação do ITA o entendimento e conceitos centrais da teoria de autômatos

- Alfabeto: um alfabeto é qualquer conjunto finito não vazio de símbolos.

- Strings: um string é uma sequência de comprimento finito de símbolos.

- Linguagens e problemas: Uma linguagem é um (possivelmente infinito) conjunto de strings, os quais escolhem seus símbolos a partir de algum alfabeto único. Quando os strings de uma linguagem têm de ser interpretados de algum modo, a questão de saber se um string pertence à linguagem às vezes se denomina um problema.

- Autômatos Finitos: Os autômatos finitos envolvem estados e transições entre estados em resposta a entradas sobre o grafo que compõe os estados. Um autômato finito tem um conjunto de estados, e seu “controle” se desloca de estado para estado em resposta a entradas “externas”.

- Linguagens Regulares: Essas linguagens são exatamente aquelas que podem ser descritas por autômatos finitos.

- Expressões Regulares: Essas expressões formam uma notação estrutural para descrever os mesmos padrões que podem ser representados por autômatos finitos.

- Gramáticas livres de contexto: essas gramáticas constituem uma notação importante para descrever a estrutura de linguagens de programação e conjuntos de strings inter-relacionados.

- Maquina de Turing: Essas máquinas são autômatos mais complexos que modelam o poder dos computadores reais. Ela nos permite estudar as questões de decibilidade.