Teoria das linguagens Formais foi desenvolvida por volta de 1950 para desenvolver teorias relacionadas às linguagens naturais, porém viu-se que estas teorias também eram aplicáveis às linguagens artificiais, originárias da Ciência da Computação. Desde então houve um desenvolvimento significativo da Análise Léxica, Sintáxe de linguagens de programação, modelos de sistemas biológicos e, recentemente, até mesmo no tratamento de linguagens não-lineares, como Planares, Espaciais e n-Dimensionais.
A sintaxe trata das propriedades livres da linguagem, como por exemplo a verificação gramatical de programas, já a semântica é voltada à interpretação de uma linguagem, como por exemplo um significado ou valor para um determinado programa. 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 pode ser vista de duas formas:
- Uma entidade livre, ou seja, sem qualquer significado associado;
- Uma entidade juntamente à uma interpretação do seu significado;
Os formalismos das linguagens lineares abstratas podem ser classificados nos seguintes tipos:
- Operacional: Também conhecido como Reconhecedor, define-se um autômato ou uma máquina abstrata, baseada em estados, em instruções primitivas e na especificação de como cada instrução modifica cada estado.
- Axiomático: Também conhecido como Gerador, associam-se regras às componentes da linguagem.
- Denotacional: Também conhecido como Funcional, define-se uma função que caracteriza o conjunto de palavras admissíveis na linguagem.
Visto que estes formalismos são aplicados à qualquer modelo matemático, as bases que tomamos para iniciar o estudo das linguagens formais também são conhecidas da matemática convencional, são eles: A teoria dos Conjuntos, relações, funções, Lógica e Técnicas de Demonstração, bem como os conceitos de Alfabeto, Palavras, Linguagens e Gramáticas.
- Conjunto: É uma coleção de zero ou mais objetos distintos, denominados Elementos do conjunto. Um elemento é uma entidade básica a qual não é definida formalmente. As operações dos conjuntos são: União, intersecção, diferença, complemento, conjunto das partes, produto cartesiano. Tais operações não serão detalhadas neste artigo.
- Relações: É um subconjunto de um produto cartesiano. Existem quatro tipos de relações: Reflexiva, Simétrica, Antissimétrica, Transitiva.
- Funções: É uma relação onde cada elemento do domínio está relacionado com, no máximo, um elemento do contra-domínio. Existem funções Injetoras, Sobrejetoras e Bijetoras ou Isomórficas.
- Lógica: A lógica aqui tratada é referente à Lógica Booleana, que estuda os princípios e métodos usados para distinguir sentenças verdadeiras ou falsas.
- Técnicas de Demonstração: Dado um teorema, partimos do ponto em que descobrimos hipótese e tese, então utilizamos técnicas para comprovar que a hipótese implica a tese. As principais técnicas de demonstração são:
- Prova Direta: Simplesmente pressupõe verdadeira a hipótese e, a partir desta, prova ser verdadeira a tese.
- Prova por Contraposição: parte do resultado que se A=>B então B=>A
- Prova por Redução ao absurdo: Em latim, Reductio ad Absurdum, pressupõe falsa a hipótese, se não conseguir provar sua falsidade, portanto o teorema é verdadeiro.
- Prova por indução: uma tese base é provada e uma regra de indução é usada para provar uma série de outras teses.
- Alfabeto: É um conjunto finito de Símbolos, portanto pode ser um conjunto vazio.
- Palavra: É uma seqüência finita de símbolos (do alfabeto) justapostos.
- Gramáticas: É uma quádrupla ordenada G = (V,T,P,S) onde
- V: Conjunto finito de símbolos variáveis ou não-variáveis;
- T: Conjunto finito de símbolos terminais disjuntos de V;
- P: Conjunto finito de pares, denominados regras de produção tal que a primeira componente é palavra de (V U T)+ e a segunda componente é palavra de (V U T)*;
- S: Elemento de V denominado variável inicial.
Com estes conceitos básicos podemos passar para o estudo das Linguagens Regulares