Linguagens formais

Uma linguagem formal é uma espécie de generalização da ideia de linguagem a que estamos acostumados no dia a dia.

Conceitos básicos

Para começar, podemos imaginar uma linguagem formal como uma língua comum, por exemplo o português. De que se compõe uma língua assim? Ela se compõe de palavras, que depois juntamos em frases. As frases não vão nos interessar, só as palavras. De que se compõem as palavras? De letras do alfabeto. Por isso vamos começar pelo alfabeto.

Alfabeto é qualquer conjunto não vazio. Os elementos do alfabeto são chamados de símbolos. No caso do português, será o alfabeto usual, com letras minúsculas e maiúsculas, além das variantes com acentos, til e cedilha. Se quiséssemos descrever não o português, mas, por exemplo, números, teríamos no alfabeto os dez algarismos. O alfabeto costuma ser representado pelo símbolo Σ.

Por palavra, ou também cadeia, entendemos uma sequência finita de símbolos de algum alfabeto Σ. Se tivermos, por exemplo, o alfabeto Σ= {a,b,c,d,e,…, z}, então uma palavra é, por exemplo, a sequência “oi” ou “doberman”, mas já não “coração” (não temos as letras “ç” e “ã”), “Pedro” (não temos a letra “P” maiúscula) nem “bom dia” (não temos o espaço). O comprimento de uma palavra é o número de símbolos de que ela se compõe.

Concatenação de palavras: se tivermos duas palavras a = a₁a₂… a_n e b = b₁b₂… b_m, a concatenação delas dá a palavra ab = a₁a₂… a_nb₁b₂… b_m. Exemplo: concatenando as palavras “oi” e “doberman”, obtemos a palavra “oidoberman”. A concatenação se representa por uma bolinha, ou seja, a ∘ b, ou então não se usa nenhuma marca e simplesmente se escrevem as palavras uma depois da outra, sem símbolo especial para a concatenação.

A palavra vazia é representada por ε e é a palavra de comprimento zero. Se concatenarmos uma palavra a = a₁… a_n com a palavra vazia ε, obtemos de volta a palavra a. Ou seja, vale a ∘ ε = a.

O fecho do alfabeto Σ é o conjunto de todas as palavras que conseguimos formar com o alfabeto Σ, incluindo a palavra vazia. O fecho se representa por Σ^∗. Se tivermos o alfabeto binário Σ= {0, 1}, então vale

$${\mathrm{\Sigma }}^{\ast }=\{\epsilon ,0,1,00,01,10,11,000,001,\dots \}$$

Às vezes usamos também o fecho positivo do alfabeto, que é, de novo, o conjunto de todas as palavras que conseguimos formar com o alfabeto, exceto a palavra vazia. O fecho positivo se representa por Σ⁺ e vale Σ⁺ = Σ^∗ ∖ {ε}.

Exemplos de alfabetos

• Voltemos ao exemplo do português. Toda palavra do português está no fecho de um alfabeto que contém as letras minúsculas e maiúsculas e as variantes com acentos (e talvez ainda o hífen “-”). Se a esse alfabeto acrescentarmos o espaço e os sinais de pontuação (vírgula, ponto, exclamação, interrogação, …), o fecho conterá todas as frases que conseguimos formar em português. É claro que esse fecho também conterá frases como “sadflsf kasdf kagrjewiçãoáéíóúker kf fkjbsjbgvbadfgsa!!!:??: ::!?:?:sdf”, que, mesmo assim, ainda fazem mais sentido do que muitos comentários que lemos na internet.

• Se o nosso alfabeto contiver todos os algarismos Σ= {0, 1, …, 9}, então o fecho conterá todos os números naturais — e ainda alguns a mais. Isso porque também haverá nele números que começam com zero, por exemplo 00054, ou o próprio zero, e ainda a palavra vazia, que, é claro, não é número algum.

• O alfabeto tem de ser não vazio, de modo que o menor alfabeto tem pelo menos um símbolo. Por exemplo, para o alfabeto Σ= {!} obteríamos o fecho Σ^∗ = {ε, !, !!, !!!, !!!!, …}, ou seja, um conjunto de palavras em que, para cada n ∈ ℕ, existe no fecho a palavra que tem n pontos de exclamação, e nenhuma outra palavra estará no fecho.

• Seja Σ= {qw,c}. Esse é um alfabeto muito estranho, porque contém a palavra qw. Essa notação normalmente não se usa, porque é confusa e esquisita, mas podemos imaginar que grudamos as letras “q” e “w” de modo que formem um único caractere. Então podemos ver a palavra “qw” como o símbolo “qw”. Se com esse símbolo formássemos a palavra “qwcqw”, essa palavra teria comprimento três — seria composta dos símbolos “qw”, “c” e “qw”. Não encontramos alfabetos assim com muita frequência, mas existem situações em que precisamos usar símbolos desse tipo, compostos de vários símbolos.

Linguagem formal

Uma linguagem (formal) sobre o alfabeto Σ é qualquer subconjunto de Σ^∗. Para uma linguagem L sobre o alfabeto Σ, vale portanto L ⊆ Σ^∗. Exemplos de linguagens:

• Na parte anterior definimos o alfabeto dos algarismos Σ= {0, 1, …, 9}. O fecho é formado por todas as palavras compostas apenas de algarismos. Se acrescentarmos a regra de que a palavra não pode começar com zero e não pode ser vazia, obtemos o conjunto dos números naturais positivos ℕ^*. Vale a relação ℕ^* ⊆ Σ^∗, de modo que ℕ^* é uma linguagem sobre o alfabeto Σ.

• Ao conjunto de algarismos anterior podemos acrescentar ainda o sinal de menos “-”, de modo que Σ= {0, 1, …, 9, −}. O fecho é formado por todas as palavras compostas de algarismos ou do sinal de menos. Isso, porém, significa que no fecho há também palavras como “12-84-”, “1-5-8” ou “-”. Criamos a linguagem dos números inteiros ℤ acrescentando três regras:

  • O sinal de menos não aparece na palavra de forma alguma ou aparece no início da palavra.
  • O primeiro algarismo da palavra não pode ser zero, exceto na palavra “0”.
  • Toda palavra deve conter pelo menos um algarismo.

  Esse conjunto descreve o conjunto dos números inteiros e é um subconjunto de Σ^∗ — ou seja, é uma linguagem sobre o alfabeto Σ.

• Seja Σ= {0, 1}. O fecho é, assim, formado por todas as palavras compostas de zeros e uns. Podemos definir uma linguagem L sobre esse alfabeto, por exemplo, como o conjunto de todas as palavras que têm exatamente três uns. Podemos ser até mais criativos e dizer que a linguagem L será o conjunto de todas as palavras que representam um formato válido de arquivo docx (aquilo que sai do Word).

• Continuemos com o alfabeto binário Σ= {0, 1}. Toda cadeia de caracteres (caracteres comuns, que você tem no teclado) pode ser convertida para a forma binária, isto é, em zeros e uns, e depois de volta, por exemplo por meio da tabela ASCII (ou, mais precisamente, a tabela ASCII converte caracteres em números e os números do sistema decimal podem ser convertidos em números do sistema binário). Assim, podemos definir a linguagem de todas as palavras que correspondem a um e-mail válido, e ela continuará sendo uma linguagem sobre o alfabeto binário.

Concatenação de linguagens: podemos concatenar também linguagens. A definição será parecida com a do produto cartesiano de conjuntos. Sejam duas linguagens L₁ e L₂. A concatenação delas, L₁ ∘ L₂, dá uma nova linguagem, que definimos assim:

$$L_1\circ L_2=\{w_1\circ w_2|w_1\in L_1,w_2\in L_2\}$$

Ou seja, pegamos todas as palavras da linguagem L₁ e as concatenamos com todas as palavras da linguagem L₂. Exemplo: sejam

$$\begin{array}{rcl}{L}_1& =& \{0,1\}\\ L_2& =& \{a,b,oi\}\end{array}$$

Então vale:

$$\begin{array}{rcl}{L}_1\circ L_2& =& \{0a,0b,0oi,1a,1b,1oi\}\\ L_2\circ L_1& =& \{a0,a1,b0,b1,oi0,oi1\}\\ L_1\circ L_1& =& \{00,01,10,11\}\end{array}$$

Até agora, para descrever linguagens usamos a língua comum, ou seja, simplesmente descrevemos com palavras como a linguagem deve ser. Isso, porém, é muito pouco prático, de modo que se introduzem maneiras mais formais de definir uma linguagem. A primeira delas é a gramática.