Introdução

Uma linguagem formal, ao contrário de uma linguagem natural, tem:

Sintaxe bem definida: sempre se pode saber se uma sentença pertence à linguagem;
Semântica precisa: não contém sentenças sem significado ou ambíguas.

As linguagens formais são úteis, não apenas na matemática, mas também nas áreas que utilizam a matemática como ferramenta, como as Engenharias, a Física, a Química e a Computação. No caso da Computação as linguagens formais são usadas diretamente pela maioria dos profissionais da área no dia a dia. Exemplos de linguagens formais são as linguagens Java, C, Pascal, HTML, etc. Desde o nível de instruções de máquina até os níveis altos da programação de um computador, as linguagens formais são uma presença constante.

Conceitos Gerais

Um alfabeto (representado por $\Sigma$ (sigma) ou $\Gamma$ (gama)) é um conjunto finito não vazio de elementos que são referidos como símbolos. Uma palavra (também chamada cadeia - ou string, em inglês) sobre um alfabeto $\Sigma$ é uma sequência finita de símbolos de $\Sigma$ . O tamanho de uma palavra $x$ , $|x|$ , é o número de símbolos que a compõe. A palavra vazia – constituída por zero símbolos – é designada por $\varepsilon$ (épsilon), logo $|\varepsilon |=0$ .

Exemplo 1: Dois exemplos de alfabetos são: $\Sigma =\{1\}$ e $\Gamma =\{0,1\}$ . Exemplos de palavras sobre $\Sigma$ são $\varepsilon ,1,11,111$ etc. Já sobre $\Gamma$ podemos ter: $0,1,01,10,11,000$ etc.

Seja $a$ um símbolo. A notação $a^{n}$ , onde $n\in \mathbb {N}$ , é utilizada para designar uma palavra constituída de $n$ a’s em sequência. Assim, considerando o alfabeto $\Sigma$ do Exemplo 1, algumas de suas palavras podem ser assim escritas: $0^{3}=000$ , $1^{2}=11$ , $1^{0}=\varepsilon$ , $1^{3}01^{2}=111011$ etc. Uma linguagem sobre um alfabeto $\Sigma$ é um conjunto de palavras sobre $\Sigma$ . Se o conjunto de todas as palavras sobre $\Sigma$ é $\Sigma ^{*}$ , então uma linguagem $L$ sobre $\Sigma$ é qualquer subconjunto de $\Sigma ^{*}$ , i.e., $L\subset \Sigma ^{*}$ .

Exemplo 2: Seja o alfabeto $\Sigma =\{0,1\}$ . O conjunto de todas as palavras sobre $\Sigma$ é $\Sigma ^{*}=\{\varepsilon ,0,1,00,01,10,11,000,...\}.$ São exemplos de linguagens sobre $\Sigma$ :
$\emptyset$ , linguagem que não contém nenhuma cadeia;

$\{\varepsilon \}$ , linguagem que só contém a cadeia vazia;

$\{0\}$ , contém somente uma única cadeia: 0;

$\{\varepsilon ,0\}$ , contém duas cadeias: $\varepsilon {\text{ e }}0$ ;

$\{w\in \Sigma ^{*}|1\leq |w|\leq 5\}$ , contém $\sum _{i=1}^{5}2^{i}$ cadeias;

$\{0^{n}|n{\text{ é par}}\}$ , linguagem de tamanho infinito, já que existe uma infinidade de números pares;

$\{0^{n}1^{n}|n\in N\}$ , linguagem constituída de toda palavra de tamanho par cuja primeira metade só contém 0s e a segunda metade só contém 1s.

$\{\Sigma ^{*}\}$ , contém todas as palavras possíveis sobre o alfabeto $\Sigma$ .

A maior parte das linguagens de interesse é infinita. E sua descrição envolve o uso de regras tais como as que foram apresentadas no Exemplo 2.

Operações com linguagens

Sendo uma linguagem definida como um conjunto, é possível operar duas ou mais linguagens utilizando as mesmas operações definidas sobre conjuntos. Considere as linguagens L₁ e L₂ definidas sobre Σ₁ e Σ₂, respectivamente. Assim:

L₁∪L₂={w | w∈L₁ ou w∈L₂ } é uma linguagem definida sobre Σ1∪Σ2;
L₁∩L₂={w | w∈L₁ e w∈L₂ } é uma linguagem definida sobre Σ1∩Σ2;
L₁-L₂={w | w∈L₁ e w∉L₂ } é uma linguagem definida sobre Σ1;
O complemento de L₁ é L₁^¯={w | w∈Σ^* e w∉L₁ }=Σ^*-L₁ e é uma linguagem definida sobre Σ^*.

Existem ainda outras operações tanto sobre palavras quanto sobre linguagens. A concatenação de duas palavras x=a₁a₂…a_m e y=b₁b₂…b_n é a palavra xy=a₁a₂…a_mb₁b₂…b_n. A operação de concatenação satisfaz as seguintes propriedades:

Associatividade
Elemento neutro à direta e à esquerda

Assim, sejam as palavras x,y,e z

pela associatividade temos que x(yz)=(xy)z; pelo elemento neutro à direita e à esquerda temos que εw=wε=w para qualquer palavra w.

O reverso de uma palavra w=a₁a₂…a_n, w^R, é a sequência de símbolos na ordem inversa w^R=a_na_n-1…a₁. Uma palavra tal que w=w^R é um palíndromo. Seja uma palavra w=xyz, onde x, y e z podem ser ε ou não. A palavra z é uma subpalavra de w, x é um prefixo e y é um sufixo. Em particular, ε é prefixo, sufixo e subpalavra de qualquer palavra, e w é prefixo, sufixo e subpalavra de qualquer palavra w.