Linguagens Formais e Autômatos

A teoria das linguagens formais é parte da teoria da computação e, como tal, é imprescindível seu conhecimento por todos os profissionais e acadêmicos da área. Este material é resultado de notas de aulas da disciplina de um semestre Linguagens Formais e Autômatos ministrada para o curso de graduação em Engenharia de Computação da Pontifícia Universidade Católica de Campinas durante doze anos. Nas instituições de ensino superior, essa disciplina é basicamente teórica e importantíssima para a computação. Divididas em quatro tipos, e cada um com seu processador computacional, ou autômato, as linguagens formais (incluindo algumas questões ligadas à complexidade e à computabilidade) são apresentadas em quatro capítulos que trazem ilustrações, exercícios resolvidos e propostos.
Linguagens formais e autômatos livro trata, no Capítulo 1, de linguagens regulares e autômatos finitos (a primeira linguagem; gramáticas e linguagens; propriedades de fechamento; autômatos de estados finitos; autômatos finitos com arcos; minimização de um autômato finito; autômatos finitos com saída). No Capítulo 2 o autor fala de linguagens livres de contexto e autômatos de pilha - além do teorema da equivalência; programas, linguagens e parsing; e gramáticas livres de contexto e a língua natural. O Capítulo 3 traz linguagens sensíveis ao contexto e autômatos limitados linearmente, introduzindo no curso as máquinas de Turing. O Capítulo 4 fecha o livro falando de linguagens recursivamente enumeráveis e estendendo-se em gramáticas irrestritas e na teoria da complexidade (de tempo e espaço) de uma máquina de Turing, bem como no problema da parada e da indecibilidade.