CONCEITOS BÁSICOS DE LINGUAGENS FORMAIS

1. Introdução

A Teoria das Linguagens Formais teve seu desenvolvimento na decada de 1950, com o objetivo de desenvolver teorias relacionadas com a linguagens naturais, entretanto logo se percebeu que essa teria também era adequada para o estudo de linguagens artificiais, desde então o estudo de linguagens formais tem sido empregado para o estudos de linguagens de programação.

2. Sintaxe e semântica

Antes de mais nada definiremos o sentido dessas palavras:

 Sintaxe: É o estudo das relações entre as palavras ou vocábulos de uma determinada linguagem, seu enfoque é na estrutura da linguagem.

 Semântica: É o estudo do sentido entre os vocábulos de determinada linguagem, estudo esse que determina o que se quer dizer.

Historicamente, no estudo do entendimento de linguagens de programação, o problema sintático foi reconhecido antes do problema semântico, como consequência disso foi dada uma grande enfase a sintaxe, ao ponto de levar a ideia de que as questões de linguagens de programação eram apenas de sintaxe. Aguardou-se um certo tempo para que os teóricos em linguagens reconhecessem a necessidade de se abordar a semântica.

Uma linguagem de programação 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 linguagens como, por exemplo, a verificação gramatical de programas. A semântica objetiva dar uma interpretação para a linguagem. A sintaxe manila os símbolos sem considerar o seu significado.

Sintaticamente falando não existe um programa errado, nesse caso simplesmente não é um programa, por outro lado um programa sintaticamente correto não é aquilo que o programador esperava. Nesse contexto a consideração de certo e errado volta-se para se o programa em questão modela adequadamente um problema ou não.

Os limites entre sintaxe e semântica nem sempre são claros, contudo a distinção entre sintaxe e semântica em linguagens artificias é em geral obvia para a maioria dos problema relevantes.

3. Formalismos

No Tratamento de sintático de linguagens lineares abstratas é empregado certos formalismos que serão relacionados aqui:

 Operacional: defini-se automato ou maquina abstrata, baseada em estados, em instruções primitivas e na forma como essas instruções modifica cada estado. Uma maquina abstrata deve ser simples para que não haja condições de dubiedade na execução de seu código. Também é chamado de formalismo reconhecedor, no sentido em que permite a análise de uma determinada entrada para verificar se é reconhecida pela determinada maquina.

 Axiomático: associa-se regras aos componentes da linguagens. As regras permitem afirmar o que será verdadeiro após a ocorrência de cada clausula considerando o que era verdadeiro antes da ocorrência. A abordagem axiomática que segue é sobre gramaticas. Uma gramatica também é dita como formalismo gerador, no sentido que permite verificar se um determinado elemento da linguagem é “gerador”.

 Denotacional: Também denominado formalismo funcional. Define-se em função que caracteriza o conjunto de palavras admissíveis em cada linguagens. Em geral trata-se de funções construídas a partir de funções elementares.

4. Conjuntos e suas operações

Um conjunto é uma entidade básica a qual não é definida formalmente, quanto ao seus relacionamentos tem-se o seguinte:

 PROPRIEDADES DAS RELAÇÕES EM A

• Reflexiva

Sejam A um conjunto e R uma relação em A. Então R é uma Relação Reflexiva, se

(∀ x ∈ A) ( (x,x) ∈ R ) ou (∀ x ∈ A) (xRx )

Informalmente, uma relação é reflexiva, quando todo elemento está relacionado consigo mesmo. Um exemplo clássico é a relação de igualdade nos números reais.

• Irreflexiva

Sejam A um conjunto e R uma relação em A. Então R é uma Relação Irreflexiva ou Anti-Reflexiva, se (∀ x ∈ A) ( (x,x) ∉ R ).

• Simétrica

Sejam A um conjunto e R uma relação em A. Então R é uma Relação Simétrica, se

(∀ x,y ∈ A) ( (x,y) ∈ R → (y,x) ∈ R )

Informalmente, uma relação é simétrica, quando toda vez que um elemento estiver relacionado com outro, a vice-versa também estará relacionada.

• Anti-Simétrica

Sejam A um conjunto e R uma relação em A. Então R é uma Relação Anti-Simétrica, se

(∀ x,y ∈ A) ( ( (x,y) ∈ R ∧ (y,x) ∈ R ) → x = y )

• Transitiva

Sejam A um conjunto e R uma relação em A. Então R é uma Relação Transitiva, se

(∀ x,y,z ∈ A) ( ( (x,y) ∈ R ∧ (y,z) ∈ R) → (x,z) ∈ R )

 RELAÇÕES DE EQUIVALÊNCIA EM A

Relações de Equivalência são importantes na identificação de grupos de elementos semelhantes, segundo algum critério.

 Definição :

Seja R ⊆ A x A. Então: R é uma relação de equivalência ⇔ R é reflexiva, simétrica e transitiva.

De fato,

• É reflexiva pois: ∀ x ∈ IR, x = x ;

• É simétrica pois: ∀ x,y ∈ IR, x = y → y = x

• É transitiva pois: ∀ x,y,z ∈ IR, ( x = y ∧ y = z ) → x = z

5. CLASSES DE EQUIVALÊNCIA

Quando operamos com relações de equivalência, podemos identificar conjuntos de elementos que possuem critérios comuns