Senhor

Linguagens Formais e Autômatos

l Introdução e Conceitos Básicos
1.1 Introdução
Teoria das Linguagens Formais foi originariamente desenvolvida na década de 1950 com o objetivo de desenvolver teorias relacionadas com as linguagens naturais. Entretanto, logo foi verificado que esta teoria era importante para o estudo de linguagens artificiais e, em especial, para as linguagens originárias na Ciência da Computação. Desde então, o estudo das Linguagens Formais desenvolveu-se significativamente e com diversos enfoques, com destaque para aplicações em Análise Léxica e Sintática de linguagens de programação, modelos de sistemas biológicos, desenhos de circuitos e relacionamentos com linguagens naturais. Recentemente, inclui-se a ênfase no tratamento de Linguagens Não-Lineares, como Planares, Espaciais e n-Dimensionais.

Sintaxe e Semântica
Linguagens Formais preocupa-se com os problemas sintéticos das linguagens. Assim, inicialmente, é importante introduzir os conceitos de sintaxe e semântica de linguagens.
Historicamente, no estudo do entendimento das linguagens de programação, o problema sintético foi reconhecido antes do problema semântico e foi o primeiro a receber um tratamento adequado. Adicionalmente, os problemas sintéticos são de tratamento mais simples que os semânticos. Como consequência, foi dada uma grande ênfase à sintaxe, ao ponto de levar à ideia de que as questões das linguagens de programação resumiam-se às questões da sintaxe. Atualmente, a teoria da sintaxe possui construções matemáticas bem definidas e universalmente reconhecidas como, por exemplo, as Gramáticas de Chomsky.
Uma linguagem de programação (bem como qualquer modelo matemático) pode ser vista de duas formas:
• como uma entidade livre, ou seja, sem qualquer significado associado;
• como uma entidade juntamente com uma interpretação do seu significado.
A sintaxe trata das propriedades livres da linguagem como, por exemplo, a verificação gramatical