Alfabetos, Palavras e Linguagens

Era uma vez, num reino muito muito distante, ...

Alfabetos, Palavras e Linguagens

Símbolos e Alfabetos

Alfabeto, Símbolo. Um alfabeto é um conjunto finito de símbolos, também designados letras (em inglês: symbols, letters, tokens).

Os alfabetos são normalmente representados por maiúsculas gregas $Σ$ (sigma) e $Γ$ (gama) e os símbolos por minúsculas romanas $a, b, c, d$ .

Por exemplo:

O alfabeto do português tem os seguintes símbolos: $a, b, c, \dots, x, y, z$ .
Os símbolos $0$ e $1$ formam um alfabeto binário. Outro alfabeto binário muito usado em ALP é ${a, b}$ .
Os números naturais podem ser escritos em base 10 usando o alfabeto ${0, 1, 2, 3, 4, 5, 6, 7, 8, 9}$ .
Para as expressões algébricas usa-se o alfabeto ${0, 1, \dots, 8, 9} \cup {+, -, \times, \div, (,)}$ .

As linguagens de programação têm um conjunto de palavras reservadas, como while, if, etc. que são atómicas, isto é, não podem ser divididas.

O símbolo "if" não é, em termos da linguagem de programação, um "i" seguido de um "f", mas um símbolo que não pode ser decomposto.

Já fragmentos de programas como if (x == 42) { return "yes"; } else { return "no"; } são compostos. Nesta instrução condicional (x == 42) é o teste (ou guarda), { return "yes"; } o bloco positivo e { return "no"; } o bloco negativo. Neste caso a instrução resulta de uma regra do tipo

Condicional := if ( Condição ) { Instruções } else { Instruções }

Por sua vez a guarda (Condição) e os blocos de Instruções podem ser decompostos, até chegarmos a símbolos atómicos como (, ==, return, etc.

Palavras

Palavra. Uma palavra sobre um alfabeto $Σ$ é uma sequência finita de símbolos desse alfabeto (em inglês: word).

Formalmente, uma palavra de comprimento $n$ é uma função $p : {1, 2 \dots, n} \to Σ$ que a cada inteiro $i \in {1, 2, \dots, n} \mapsto p (i) \in Σ$ .

As palavras são normalmente representadas pelas minúsculas romanas $p, q, u, v, w, x, y, z$ .

Palavra Vazia. A palavra vazia (em inglês: empty word, null, nil) é a única palavra de comprimento 0 e representa-se pela letra grega $λ$ (lambda). Também é comum usar-se $ϵ$ ou $ε$ (epsilon) para representar a palavra vazia.

Não confundir a palavra $λ$ (que tem comprimento 0) com um símbolo. Estes, como palavras, têm comprimento um.

Propriedades do Comprimento das palavras

O comprimento da palavra $p$ é normalmente representado por $∣ p ∣$ .
Para a palavra vazia, $∣ λ ∣ = 0$ . Em geral, se $p = a_{1} \dots a_{n}$ então $∣ p ∣ = n$ . Isto é, $∣ a_{1} \dots a_{n} ∣ = n$ .

Fecho de Kleene

Dado um alfabeto, interessa considerar todas as palavras que podem ser formadas com essas letras.

Por exemplo, para representar números em binário usam-se palavras sobre ${0, 1}$ . Mas, depois de se definirem todas as palavras, há que determinar quais as que interessam. Por exemplo, embora $00$ e $0$ sejam palavras binárias (distintas), se interpretadas normalmente, ambas correspondem ao número $0$ e portanto há aqui uma ambiguidade. Será possível definir uma linguagem que continue a representar todos os números mas sem ambiguidades?

Para abordar estas questões tem de se começar por definir rigorosamente o conjunto de todas as palavras que se podem obter com um dado alfabeto.

Fecho de Kleene. O fecho do alfabeto $Σ$ é o conjunto de todas as palavras sobre $Σ$ , representa-se por $Σ^{*}$ e fica definido pelas seguintes condições:

base $λ \in Σ^{*}$ .

passo Se $p \in Σ^{*}$ e $a \in Σ$ então $p a \in Σ^{*}$ .

fecho Qualquer palavra $p \in Σ^{*}$ só pode ser obtida por um número finito de aplicações do passo a começar na palavra vazia. E reciprocamente, qualquer palavra obtida a partir de $λ$ por aplicações do passo em número finito está em $Σ^{*}$ .

Esta definição exclui a possibilidade de palavras infinitas. Mas isto não significa que exista um limite ao comprimento das palavras em $Σ^{*}$ . Pelo contrário, se $Σ \neq = \emptyset$ então, para qualquer $n \in N$ existe pelo menos uma palavra de comprimento $n$ .

Exercício: Porquê? E porque é que acima é referida a condição " $Σ \neq = \emptyset$ "? O que é $\emptyset^{*}$ ?

No fecho de um alfabeto também ficam excluídas palavras formadas por símbolos de outros alfabetos. Por exemplo, a palavra $abc$ não está em ${a, b}^{*}$ .

Logo a primeira condição na definição de $Σ^{*}$ inclui a palavra vazia. Como muitas vezes é conveniente excluir $λ$ define-se $Σ^{+} = \cup_{n > 0} Σ^{n} = Σ Σ^{*} .$

Exercício: Mostre que $Σ^{+} = Σ^{*} ∖ {λ}$ .

Operações com Palavras

Comprimento

Ainda não foi apresentada uma definição rigorosa de comprimento de uma palavra. Usando um esquema recursivo:

Comprimento. A função comprimento é calculada pelas seguintes regras:

base $∣ λ ∣ = 0$ .

passo $∣ p a ∣ = ∣ p ∣ + 1$ , com $p \in Σ^{*}, a \in Σ$ .

Por exemplo, para calcular $∣ abc ∣$ :

Como $abc \neq = λ$ , aplicar-se a regra do passo: fazendo $p a = abd$ tem de ser $p = ab$ e $a = c$ , e obtem-se $∣ abc ∣ = ∣ ab ∣ + 1$ .
Ainda não está calculado o valor de $∣ ab ∣$ . Tornando a aplicar o passo: $∣ ab ∣ = ∣ a ∣ + 1$ .
Uma nova aplicação do passo: $∣ a ∣ = ∣ λ ∣ + 1$ .
Finalmente, pela base: $∣ λ ∣ = 0$ , portanto $∣ a ∣ = 0 + 1 = 1$ e, sucessivamente, obtém-se $∣ ab ∣ = 2$ e $∣ abc ∣ = 3$ .

Também é comum usar-se a notação $∣ p ∣_{a}$ para indicar o número de ocorrências do símbolo $a$ na palavra $p$ .

Por exemplo: $∣ aba ∣_{a} = 2, ∣ aba ∣_{b} = 1$ .

Concatenação

O operação fundamental das palavras é a "concatenação". A concatenação de hello com world é helloworld. Para definir rigorosamente esta operação:

Concatenação. A concatenação (ou produto) de duas palavras $u, v \in Σ^{*}$ representa-se por $u \cdot v$ ou apenas $uv$ e é uma operação binária definida por:

base Se $v = λ$ então $u \cdot v = u$ .

passo Se $∣ v ∣ = n > 0$ então

Existe uma palavra $w \in Σ^{*}$ e uma letra $a \in Σ$ tal que $v = w a$ .

$u \cdot v = (u \cdot w) a$ .

Por exemplo, para calcular a concatenação de $ab$ com $cd$ :

O comprimento de $cd$ é 2, portanto temos de aplicar o passo: $ab \cdot cd = (ab \cdot c) d$ .
Precisamos de calcular $ab \cdot c$ . Pela regra do passo: $ab \cdot c = (ab \cdot λ) c$ .
Finalmente, $ab \cdot λ$ é calculada pela regra base: $ab \cdot λ = ab$ .
Andando para trás: $ab \cdot c = (ab \cdot λ) c = (ab) c = abc$ e, portanto, $ab \cdot cd = (ab \cdot c) d = abcd$ .

Potência

A repetição de concatenações define as potências, tal como a multiplicação dos números.

Potências. As potências da palavra $p \in Σ^{*}$ são (informalmente): $p^{0} = λ, p^{1} = p, p^{2} = pp, \dots, p^{n} = p^{n - 1} p .$

Por exemplo, $(01)^{2} = 0101$ mas $01^{2} = 011$ , seguindo as regras normais de precedência das operações.

Inversa

Finalmente, as palavras (enquanto sequências de símbolos) podem ser escritas "de trás para a frente":

Inversa. A inversa de $p \in Σ^{*}$ , representada por $p^{R}$ (ou $p^{- 1}$ ) é calculada pelas seguintes regras:

base Se $p = λ$ então $p^{R} = p$ .

passo Se $∣ p ∣ = n > 0$ então $p = q a, a \in Σ$ e $p^{R} = a q^{R}$ .

Por exemplo, se $p = abcd$ então $p^{R} = dcba$ .

Propriedades das Operações de Palavras

O que acontece à inversa de duas palavras concatenadas?

Para quaisquer palavras $u, v \in Σ^{*}$ , $(uv)^{R} = v^{R} u^{R}$

Demonstração (informal): Se $u = λ$ a conclusão é evidente. Caso contrário $u = u_{1} u_{2} \dots u_{n}$ e $v = v_{1} v_{2} \dots v_{m}$ com todos os $u_{i}, v_{j} \in Σ$ . Então: $(uv)^{R} = (u_{1} u_{2} \dots u_{n} v_{1} v_{2} \dots v_{m})^{R} = v_{m} \dots v_{2} v_{1} u_{n} \dots u_{2} u_{1} = (v_{m} \dots v_{2} v_{1}) (u_{n} \dots u_{2} u_{1}) = v^{R} u^{R} □$

O fecho também tem propriedades interessantes.

Se $Σ, Γ$ forem alfabetos,

$Σ^{*} = \cup_{n \geq 0} Σ^{n}$ .

$Σ \subseteq Σ^{*}$ .

$\emptyset^{*} = {λ}$ .

Se $Σ \neq = \emptyset$ então $Σ^{*}$ é infinito.

Se $Σ \subset Γ$ então $Σ^{*} \subset Γ^{*}$ .

Por fim, a concatenação tem propriedades semelhantes às do produto (de números).

Sejam $u, v, w \in Σ^{*}$ .

associativa $u (v w) = (uv) w$ .

elemento neutro $u λ = λ u = u$ .

não comutativa Em geral, $uv \neq = vu$ .

aditiva $∣ uv ∣ = ∣ u ∣ + ∣ v ∣$ .

unicidade Cada palavra só pode ser escrita de uma única forma como concatenação de símbolos. Isto é, se $u = v$ e $u = u_{1} \dots u_{n}$ e $v = v_{1} \dots v_{m}$ então $n = m$ (mesmo comprimento) e $u_{i} = v_{i}$ para cada $i = 1, \dots, n$ (mesmos símbolos) .

Ordenações de Palavras

Uma palavra pode "conter" outra. Por exemplo, palavra contém pala no início, ala no "meio" e lavra no fim. Estes três casos ilustram as definições que se seguem:

Subpalavra, prefixo, sufixo. Sejam $p, q, u, v \in Σ^{*}$ .

subpalavra $p \leq q$ se $q = u p v$ .

prefixo $p \leq_{P} q$ se $q = p v$ .

sufixo $p \leq_{S} q$ se $q = u p$ .

Fica claro que os prefixos são casos particulares das subpalavras (quando $u = λ$ ) e que cada palavra é subpalavra de si própria (quando $u = λ = v$ ).

Outro caso importante é a ordem lexicográfica (dos dicionários), onde se usa a ordem das letras para ordenar as palavras.

Ordem Lexicográfica. Supondo que o alfabeto está ordenado, $Σ = {a_{1} < a_{2} < \dots < a_{n}}$ . Então $p \leq_{L} q$ se:

$p \leq_{P} q$ .

Caso contrário, $p = u s_{i} v$ e $q = u s_{j} w$ com $s_{i} < s_{j}$ .

Esta definição abrange dois casos:

por < porque porque por é um prefixo de porque.
porque < portugal porque, como porque = por_q_ue e portugal = por_t_ugal então portugal e porque têm um prefixo comum, por, e "divergem primeiro" nas letras q e t. Como q < t então porque < portugal.

A ordem lexicográfica tem um problema interessante: Quantas palavras existem entre $0$ e $1$ , num alfabeto binário?

Por exemplo $00 <_{L} 1$ [Exercício: porquê?]. Mas também $000 < 1$ . De facto, $0^{n} < 1$ para qualquer $n > 0$ . Portanto, seguindo a ordem lexicográfica, há infinitas palavras entre $0$ e $1$ .

Esta conclusão, embora dramática, mostra que a ordem lexicográfica é inútil na importante tarefa de enumerar (isto é, listar) todas as palavras por ordem. Para resolver este problema é necessária mais uma ordem entre palavras:

Ordem Mista. Dadas duas palavras $p, q \in Σ^{*}$ , $p \leq_{M} q$ se $∣ p ∣ < ∣ q ∣$ ou ( $∣ p ∣ = ∣ q ∣$ e $p \leq_{L} q$ ).

Dito de outra forma, a ordem mista define o seguinte processo:

Primeiro, as palavras são agrupadas por comprimentos iguais: todas as palavras de comprimento 0 antes das de comprimento 1, todas as de comprimento 1 antes das de 2, etc.
Depois, em cada grupo, as palavras (todas com o mesmo comprimento) são ordenadas lexicograficamente.

Revisitando o exemplo anterior:

$0$ e $1$ têm o mesmo comprimento. Portanto, são comparadas lexicograficamente: $0 <_{M} 1$ porque $0 <_{L} 1$ .
O comprimento de $00$ é maior que o de $1$ . Portanto, $1 <_{M} 00$ .
$01$ e $10$ têm o mesmo comprimento. Lexicograficamente, $01 <_{L} 10$ portanto $01 <_{M} 10$ .

De facto a ordem mista é uma ferramenta essencial porque permite "avançar passo-a-passo" no conjunto de todas as palavras, sem deixar nenhuma de fora. Mais concretamente:

A ordem mista define uma sequência de todas as palavras. No caso do alfabeto binário, com $0 < 1$ :

$λ <_{M} 0 <_{M} 1 <_{M} 00 <_{M} 01 <_{M} 10 <_{M} 11 <_{M} 000 <_{M} \dots$

Sucessor

A ordem mista permite começar na primeira palavra, avançar para a seguinte, depois para a seguinte, etc. da mesma forma são contados os números: 0, 1, 2, etc.

A passagem de um número para o seguinte (x++) tem nome, sucessor, que também se aplica às palavras:

Sucessor. Seja $Σ = {a_{1} < a_{2} < \dots < a_{n}}$ um alfabeto ordenado. A função sucessor tem assinatura $σ : Σ^{*} \to Σ^{*}$ e calcula-se pelas seguintes regras:

base $σ (λ) = a_{1}$ .

passo Se $i < n$ então $σ (p a_{i}) = p a_{i + 1}$ . Caso contrário, $σ (p a_{n}) = σ (p) a_{1}$ .

Voltando ao exemplo anterior: $σ (λ) = 0, σ (0) = 1, σ (1) = σ (λ) 0 = 00, \dots$

Visto de outra forma, usando o sucessor obtém-se uma sequência que começa na palavra vazia e percorre todas as palavras:

$λ \to σ 0 \to σ 1 \to σ 00 \to σ \dots$

Há uma clara relação entre a ordem mista e a função sucessor.

Seja $p_{0} <_{M} p_{1} <_{M} p_{2} <_{M} \dots$ a sequência de todas as palavras de $Σ^{*}$ que se obtém com a ordem mista e $p \in Σ^{*}$ uma palavra qualquer.

$p <_{M} σ (p)$ .

Se $p \neq = λ$ então existe uma palavra $q \in Σ^{*}$ tal que $p = σ (q)$ .

$p_{i + 1} = σ (p_{i})$ .

O que este teorema afirma, especialmente na igualdade $p_{i + 1} = σ (p_{i})$ , é que a ordem mista e a função sucessor são aspetos diferentes da mesma enumeração das palavras.

Linguagens

Numa linguagem de programação nem todas as palavras possíveis correspondem a programas válidos. Por exemplo:

2 return) *
    : dobro def (x

é uma palavra que pode ser formada com o alfabeto do python, mas não é um programa.

É necessário, de alguma forma, distinguir as palavras que são "válidas" das outras que não o são. De novo, encontramos na matemática exatamente as ferramentas necessárias.

Linguagem. Uma linguagem é um conjunto de palavras sobre um certo alfabeto. Isto é, $A$ é uma linguagem sobre $Σ$ se $A \subseteq Σ^{*}$ .

Esta definição de linguagem parece dizer pouco, mas por enquanto serve exatamente para o que se pretende.

Por exemplo, se $Π$ for a linguagem dos programas python então $print (2 + 40) \in Π$ mas $+) 40print 2 (\neq \in Π$ .

Mais tarde será enunciado e tratado o Problema Principal de ALP:

Problema Principal de ALP (versão 0). Dada uma linguagem $A$ e uma palavra $p$ no mesmo alfabeto, determinar se $p \in A$ .

Entretanto, como uma linguagem é (apenas) um conjunto de palavras, tem um certo número de elementos, que pode ser infinito (quantos programas python existem?): Se $A$ for uma linguagem, $∣ A ∣$ representa o número de elementos de $A$ .

Outros exemplos de linguagens são:

binárias ${0, 1}$ , ${λ, 0, 00, 000, \dots}$ , etc.
As palavras do português, sobre o alfabeto romano. Por exemplo, a, aba, abade, etc. mas não aa, prof, tásse, xkcd, etc.
Os programas de uma linguagem de programação.
As frases do português, sobre o alfabeto formado pelas palavras do português. Por exemplo bom dia, a aula é longa, etc. mas não dia dia dia, aula a é longa, etc.

Muitas vezes é útil visualizar-se uma linguagem de forma a explorar a estrutura das suas palavras. Isso pode ser feito através de árvores:

Árvore de uma Linguagem. Seja $A \subseteq Σ^{*}$ uma linguagem sobre $Σ$ .

Os vértices (ou nós) da árvore de $A$ (ou diagrama de $A$ ) são palavras de $Σ^{*}$ e cada aresta (ou arco) tem um símbolo de $Σ$ . Além disso, todas as arestas são da seguinte forma: se $p \in Σ^{*}$ e $a \in Σ$ então $p \to a p a$ é uma aresta. A raíz da árvore é a palavra vazia.

Cada vértice é representado por um círculo com a respetiva palavra lá dentro. Uma palavra da linguagem $A$ é representada por um círculo duplo.

Por exemplo, $A = {01, 011, 11, 101} \subseteq {0, 1}^{*}$ tem a seguinte árvore (onde os vértices irrelevantes foram omitidos):

Árvore (parcial) de $A = {01, 011, 11, 101}$

As palavras de $A$ estão em círculos duplos.

Operações com Linguagens

Como conjuntos, as linguagens podem ser combinadas pelas operações comuns: união, intersecção, etc. Além disso, como os seus elementos são palavras, podem ser definidas operações adicionais, específicas das linguagens (concatenação, fecho, etc).

Operações com Linguagens. Sejam $A, B$ linguagens sobre $Σ$ . Estão definidas as seguintes operações de conjuntos:

união $A \cup B = {p : p \in A \lor p \in B}$ .

intersecção $A \cap B = {p : p \in A \land p \in B}$ .

subtração $A ∖ B = {p : p \in A \land p \neq \in B}$ .

complemento $\overline{A} = Σ^{*} ∖ A$ .

Adicionalmente, usando as operações de palavras:

concatenação $A B = {pq : p \in A \land q \in B}$ .

potências $A^{0} = {λ}, A^{1} = A, A^{2} = AA, \dots, A^{n + 1} = A A^{n}$ .

fechos $A^{*} = A^{0} \cup A^{1} \cup A^{2} \cup \dots, A^{+} = A A^{*}$ .

inversão $A^{R} = {p^{R} : p \in A}$ .

Alguns exemplos das operações específicas das linguagens: Sejam $A = {a, b, ac}, B = {λ, a, c}$ . Então:

$A B = {a, b, ac} {λ, a, c} = {a λ, aa, ac, b λ, ba, bc, ac λ, aca, acc} = {a, aa, ac, b, ba, bc, aca, acc}$ .
- As palavras de $A B$ foram formadas escolhendo primeiro uma palavra de $A$ e depois uma palavra de $B$ .
- A palavra $ac$ pode ser obtida de suas formas: $a \cdot c$ e $λ \cdot ac$ .
$B^{2} = BB = {λ, a, c} {λ, a, c} = {λ, a, c, aa, ac, ca, cc}$ .
$A^{0} = {λ}; A^{2} = {aa, ab, aac, ba, bb, bac, aca, acb, acac}, \dots$ .
$A^{R} = {a, b, ca}, B^{R} = {λ, a, c} = B$ .

Confusões com a palavra vazia, o conjunto vazio, etc.

A palavra vazia, $λ$ , não é um símbolo. Qualquer símbolo, como palavra, tem comprimento 1. A palavra vazia tem comprimento 0.

O conjunto vazio, $\emptyset$ , tem 0 elementos. Para tornar este facto mais explícito também se escreve $\emptyset = {}$ .

O conjunto ${λ}$ tem um elemento, $λ$ . Portanto, não é o conjunto vazio.

Exemplo. Aqui (e só no âmbito deste exemplo) estamos a distinguir explicitamente os símbolos usando plicas, como em 'a', e as palavras usando aspas, como em "ab".

O alfabeto {a, b} tem dois símbolos: 'a' e 'b'.
Uma palavra é uma (qualquer) sequência finita de símbolos.
- Por exemplo "abba", "baba", "aa", etc.
Todas as palavras de comprimento 2 são "aa", "ab", "ba", "bb".
Também poderíamos listar todas as palavras de comprimento 3 (num total de oito palavras), etc.
Todas as palavras de comprimento 1 são "a" e "b".
- Se quiséssemos ser terrivelmente rigorosos, teríamos de dizer que 'a' e "a" são diferentes porque 'a' é um símbolo e "a" é uma sequência de símbolos, tal como, por exemplo, o inteiro 1 é completamente diferente de [1], que é uma lista de inteiros.
- Raramente é necessário distinguir explicitamente os símbolos das palavras de comprimento um.
Só há uma palavra com comprimento zero. Como sequência, "" é a (única) com zero símbolos. Em vez de "" escreve-se λ (ou ε ou ϵ).
- λ não é um símbolo mas uma palavra. Escrita por extenso é "".
Usando a concatenação de palavras podemos escrever, por exemplo: "abba" = "ab" · "ba".
- Outras formas de obter "abba" são "abba" = "a" · "bba", "abba" = "abb" · "a", etc.
- Em particular também "abba" = "abba" · λ ou "abba" = λ · "abba" ou mesmo "abba" = λ · "a" · λ · "bba".
- Nestes exemplos o λ nunca aparece entre "..." pois isso é o equivalente a um erro sintático. Também não escrevemos 2 */ 3 quando fazemos contas...
Em geral não se escrevem os símbolos como 'a', as palavras como "abab" nem as concatenações como "aa" · "ba".
- Portanto, em vez de "abba" = λ · "a" · λ · "bba" o que escrevemos é simplesmente abba = λaλbba.
- Este abuso de notação pode facilitar a leitura errada de λ como um símbolo, à semelhança de a e b.

Autómatos e Linguagens de Programação