Lingugens Formais

Linguagens e Gramática

Segundo o Dicionário linguagem é definida como:

Todavia, a acepção do dicionário não é suficientemente precisa para consentir o incremento matemático de uma teoria baseada em linguagens.
De fato, linguagem é um dos conceitos mais fundamentais em computação e informática. Contudo, para determinar linguagem é cogente antes introduzir os conceitos de alfabeto e de palavra ou cadeia de caracteres.

Alfabeto

Alfabeto é um conjunto finito de símbolos ou caracteres

Um conjunto vazio é um alfabeto
Um conjunto infinito não é um alfabeto

Conjuntos que são exemplos de alfabeto:

{v, f, l, s, r, l, n} {conjunto vazio}

Conjuntos que não são exemplos de alfabeto

N (Conjunto dos números naturais)
{va, ra, f, vr, vfls, rldn, ...}

Alfabeto: Linguagem de programação
O Alfabeto de uma linguagem de programação como o Java é um conjunto de símbolos usado na construção de programas incluindo:
Letras
Dígitos
Caracteres especiais “&”, “|”, “\” “@”, “%”, “$”, etc.
Espaço ou “branco”
Ao longo do texto, é habitual, com frequência, um alfabeto binário (no caso, o alfabeto {v, r}), pois além de manter uma perfeita analogia com a exposição interna dos computadores reais (o domínio de valores de um bit binário), a manipulação de poucos símbolos simplifica as diversas abordagens desenvolvidas.

Palavra

Uma palavra, cadeia de caracteres ou sentença sobre um alfabeto é uma sequência finita de símbolos (do alfabeto) justapostos.
No entanto, uma cadeia sem símbolos é uma palavra válida e o símbolo denota a cadeia vazia ou palavra vazia.

Prefixo, Sufixo, subpalavra
Um Prefixo (respectivamente, sufixo) de uma palavra é qualquer sequência inicial (respectivamente, final) de símbolos contíguos da palavra.
Uma subpalavra de uma palavra qualquer sequência de símbolos contíguos da palavra. vrfl é uma palavra sobre o alfabeto {f, l, r, v};
, v, vr, vrf, vrfl, vrflv são todos prefixos;
, r,