Problema 2.18

Antes de apresentar uma solução possível para este problema preciso fazer um passeio por algo conhecido por autómatos finitos de que irão ouvir falar na cadeira de Teoria da Computação I. De modo simples um autómato finito (AF) é uma máquina de estados. Quando se encontra num dado estado recebe um comando e reage a ele transitando de estado e, eventualmente, realizando alguma acção. Um exemplo concreto, embora redutor, é o caso de um interruptor. Tem associado dois estados de uma lâmpada, acesa e apagada . A transição de estado é comandada pela manipulação do interruptor. Se estiver acesa e eu carregar no interruptor passa para o estado apagada e apaga-se a luz. E inversamente, se estiver no estado apagada e se manipular o interruptor passa para o estado acesa e a luz acende-se. Claro que se estiver acesa e eu der o comando de acender, tudo se mantém nas mesma. E o mesmo para o caso de apagada. Normalmente visualizam-se os autómatos do modo ilustrado pela figura abaixo.

O que é que o nosso problema de pegar numa cadeia formada por palavras separadas por espaços de dimensão arbitrária, que queremos reduzir a apenas um, tem a ver com autómatos finitos?? Bom, se repararmos bem nós temos uma cadeia de caracteres. Podemos partir dela e criar uma outra, semelhante, na qual os espaços a mais foram retirados. É como se colocasse um filtro entre as duas cadeias. O filtro, analisa um caracter da primeira cadeia e decide se o deixa passar ou não. Isso depende de ter visto um caracter e, imediatamente a seguir, um outro. Tal facto é um sinal para se efectuar a filtragem. É como se tivéssemos um autómato finito com dois estados: num, não filtra, no outro filtra. A figura que mostramos a seguir pretende ilustrar a situação.

Foi com base nesta ideia que escrevemos o seguinte programa:

def um_espaco(cad):
 """
 Separa as palavras na cadeia deixando-as só com um espaço a separar.
 Implementado como um autómato de dois estados.
 Se quisermos retirar todos os espaços no início e no fim
 fazer primeiro cad = string.strip(cad)
 """
cadeia = " # cadeia vazia
estado = 1
for i in range(len(cad)):
    if estado == 1:
        if cad[i] == ' ': # espaço em branco!
            cadeia = cadeia + ' ' # espaço em branco!
            estado = 2
        else:
            cadeia = cadeia + cad[i]
    else: # estado igual a 2
        if cad[i] != ' ': # espaço em branco!
            cadeia = cadeia + cad[i]
            estado = 1
return cadeia

Analisemos o código. Partimos da cadeia cad e vamos construindo progressivamente a cadeia resultado em cadeia, que assim funciona como acumulador. Temos um nome, estado para identificar o estado em que nos encontramos: filtrar ou não. Partimos do estado de não filtrar (linha 9). Com o ciclo for (linha 10) vamos testar todos os caracteres. Depois: se estivermos no estado 1 e lermos um caracter branco , acrescentamos (é o primeiro!!) e transitamos para o estado 2 para continuar a observar (linhas (11 a 14). Se no estado 1 nos aparecer um caracter normal, fazemos uma cópia para a cadeia e continuamos no estado 1 (linha 16); se estivermos no estado 2 (eliminar espaços a mais) e nos aparece um caracter normal, copiamos essa caracter e regressamos ao estado 1 (linhas 18 a 20), caso contrário não fazemos nada. E pronto!