Construção de compiladores/Teoria das linguagens formais

Teoria das Linguagens Formais e dos autômatos é o estudo de modelos matemáticos que possibilitam a especificação e o reconhecimento de linguagens (no sentido amplo da palavra), suas classificações, estruturas, propriedades, características e inter-relacionamentos.

Uma linguagem formal é um conjunto de palavras,isto é, um conjunto finito de letras ou símbolos com um conjunto de regras para combinar estes elementos. O inventário destas letras é chamado de alfabeto na qual esta linguagem é definida. O modo formal como uma linguagem é definida é chamada de gramática formal.

Assim, podemos dizer que "Linguagens formais" são mecanismos formais para representação e especificação de linguagens, baseados na chamada "Teoria da Computação". As representações podem ser feitas por reconhecedores e geradores. Os reconhecedores são dispositivos formais que servem para verificar se uma sentença pertence ou não à determinada linguagem. São os autômatos: autômatos finitos, autômatos de pilha e Máquina de Turing. Os sistemas geradores são dispositivos formais que permitem a geração sistemática de todas as sentenças de uma linguagem. Os principais sistemas geradores disponíveis são as gramáticas, onde se destacam as gramáticas de Chomsky. Então, linguagens formais podem ser representadas de maneira finita e precisa através de sistemas com sustentação matemática.

Importância na Computação

A importância dessa teoria na Ciência da Computação é dupla: ela tanto apóia outros aspectos teóricos da Ciência da Computação (Decibilidade, computabilidade, complexidade computacional, por exemplo), como fundamenta diversas aplicações computacionais tais como processamento de linguagens, reconhecimento de padrões, modelagem de sistemas.