Linguagens Formais Autômatos e Computabilidade

Linguagens Formais, Autômatos e Computabilidade

- Linguagem: conjunto de palavras e regras gramaticais que permitem combinar palavras em sentenças sintaticamente corretas. A linguagem é formal quando pode ser representada por sustentação matemática.

A linguística formal compreende a representação da sintaxe (estrutura) e semântica (significado) das sentenças de uma linguagem.

- Alfabeto (vocabulário): conjunto finito de símbolos ou caracteres, podendo ser dígitos, letras, letras gregas, etc.

- Sentença (ou palavra definida sobre um alfabeto): qualquer sequência finita de símbolos do alfabeto. Ex: V = {0,1} → 001, 010011.

O tamanho da sentença é dado pelo número de símbolos que compõem a sentença. Ex: V = {a, b, c}; w = ab; |w| = 2.

- Sentença vazia: é aquela que não contem símbolos, tendo tamanho 0, representado por Ɛ. Ex: V* → conjunto de todas as sentenças compostas por símbolos de V, incluindo a sentença vazia → V+ = V* - (Ɛ). Ex: V = {0,1}; V* = {Ɛ, 0, 1, 00, 01, 10, 11, ...}; V+ = {0, 1, 00, 01, 10, 11, ...}.

- Linguagem (outra definição): qualquer conjunto de sentenças sobre um alfabeto, ou seja, uma linguagem L sobre um alfabeto V é um subconjunto de V*.

Conforme o número de sentenças, as linguagem se classificam em: finitas, vazias ou infinitas.

Uma linguagem pode ser representada:

• Listando as palavras (só para linguagem finita)
• Através da descrição algébrica. Ex: (anbncn | n>=1)
• Definindo um algoritmo que determina se uma sentença pertence ou não à linguagem: Reconhecimento. Ex: autômato finito.
• Definindo um mecanismo que gera sistematicamente as sentenças da linguagem. Ex: gramática.

Uma gramática serve para definir qual o subconjunto de sentenças que faz parte de uma determinada linguagem. Especifica uma linguagem potencialmente infinita de uma forma finita. Existem várias maneiras de representar a sintaxe das linguagens: BNF, diagrama de sintaxe, notação formal de gramática.

Ex: Backus Naur Form (BNF)

• :: = ;
• :: = BEGIN END
• :: = …

- Elementos:

• Não-terminais ou variáveis =
• Símbolos terminais = BEGIN; END
• Produções = :: =
• Símbolo inicial =

• Notação Formal de Gramática

Uma gramática G é definida por uma quádrupla G = (N, T, P, S):

N → conjunto finito de não-terminais

T → conjunto finito de terminais

P → conjunto finitos de regras de produção

S → conjunto finito de

Obs: N ∩ T = Ø; V = N ∪ T; S ∊ N; P = {𝛼 → 𝛽 | 𝛼 ∊ V+ e 𝛽 ∊ V*}

Ex:

G = (N, T, P, I)

N = {I, D}

T = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

P = {I → D, D → 0, D → 1, D → 2, D → 3, D → 4, D → 5, D → 6, D → 7, D → 8, D → 9)

• Convenções

Para facilitar a compreensão das expressões, são adotadas, sempre que possível, as seguintes convenções:

• N = {A, B, C, ..., T} → letras maiúsculas do início do alfabeto para símbolos não-terminais.
• T = {a, b, c, ..., t} → letras minúsculas do início do alfabeto para símbolos terminais.
• T* = {u,v, ...,z} → letras minúsculas do fim do alfabeto para sequências de terminais.
• (N ∪ T) = {𝛼, 𝛽, 𝛾, ...} → letras gregas para sequencias de variáveis e terminais.
• N ∪ T = {U, V, ..., Z}  → letras maiúsculas do fim do alfabeto para um símbolo terminal ou não terminal.

- Derivação: é uma equação de substituição efetuada de acordo com as regras de produção da gramática. Representa-se esta operação pelo símbolo ⇒. Logo:

x 𝛼 y ⇒ x 𝛽 y, se 𝛼 → 𝛽 ∊ P  e  x, y ∊ V*

Para garantir que pelo menos uma derivação seja efetuada, a notação utilizada é +⇒. Isto é:

𝛼1 +⇒ 𝛼m, se 𝛼1 ⇒ 𝛼2, 𝛼2 *⇒ 𝛼m,

        𝛼1, 𝛼2, ..., 𝛼m ∊ V*

• Sentença e Forma Sentencial

- Sentença: sequencia formada de terminais, obtida a partir do símbolo inicial da gramática desta linguagem, através de derivações sucessivas. Ex: S+ ⇒ u {u = sequência de terminais}

- Forma sentencial: uma sequência qualquer, composta de símbolos terminais e/ou não-terminais, obtida a partir do símbolo inicial da gramática através de derivações sucessivas.