Implementando uma máquina de estados finitos

Uma das bases da computação moderna. Teoria daquelas que pouca gente com muitos e muitos anos de profissão sequer ouviu falar.

Uma Máquina de Estados Finitos é uma máquina abstrata que define como certos processos. funcionam. Ela descreve desde uma linguagem até o funcionamento de um equipamento.

Classicamente a máquina contém um alfabeto, estados, onde destes temos o inicial e os possíveis estados finais e a função programa.

Uma notação razoável segue. Considere a máquina que captura a palavra 'aabb':

FSM = (Alfabeto, Estados, Inicial, Finais, Programa) FSM = ({a,b}, {q0, q1, q2, q3, q4}, q0, {q4}, {{q0,a->q1}, {q1,a->q2}, {q2,b->q3}, {q3,b->q4}})

Explicando:

1. O alfabeto diz quais são as possíveis entradas. Letras fora do alfabeto não serão reconhecidas.
2. Os estados são criados de acordo com a necessidade da função programa. Sabemos, por exemplo, que precisamos de duas letras 'a', portanto no estado inicial, em recebendo uma letra 'a' devemos mudar o estado atual (que é representado na implementação mas não tem significado na declaração formal) para o estado que aguarda receber a segunda letra 'a'.
3. Só pode existir um estado inicial, e ele deve constar no conjunto de estados.
4. Sempre devemos ter ao menos um estado final. No exemplo dado, basta que as letras parem de chegar quando o estado atual for igual ao único estado final declarado. Se o estado atual não for presente no conjunto dos estados finais quando as letras 'pararem de chegar' então temos um erro.
5. Letras ou estados desconhecidos resultam em erro. De maneira formal, um estado de erro deve ser criado, ou sua implementação terá de se virar pra explicar que tipo de erro ocorreu.

Mas como transformar isso em código executável??

Tem várias formas, mostrarei uma usando javascript, :-).

Usando um editor de códigos qualquer (até mesmo esse aqui se quiser boçalizar geral) declare um objeto que será a nossa máquina:

Assim como vimos na definição formal, a máquina deve possuir um alfabeto, estados, deve dizer qual é o estado inicial e quais os estados finais, além de possuir uma função programa. Vamos adiciona-los:

Antes de adicionarmos a função programa, algumas considerações sobre a mesma:

1. Dada uma letra da stream e um estado, recebemos um novo estado.
2. Não podemos dizer que as produções são ordenáveis, mas os pares de entrada são certamente únicos. Não podemos ter, por exemplo, {q1,a->q2} e {q1,a->q3}.
3. Podemos ter várias produções cuja saídas sejam idênticas, sem problemas.
4. Não há problemas caso o estado de entrada seja igual ao estado de saída.

Minha implementação para a função programa é um simples mapa, um objeto literal do javascript. cada letra do alfabeto será uma chave, e cada chave terá por membro um estado. E cada estado tem outro estado como membro... É melhor ver abaixo, fará mais sentido:

Sacou?

E sim, poderíamos usar o estado como chaves no lugar das letras do alfabeto e o alfabeto como membros dos estados de entrada, mas aí haveriam chances consideráveis de, em caso de erro, ganharmos um undefined prematuro e por conseguinte um erro bem mais difícil de tratar.

Vamos agora adicionar uma função chamada aceitar, que servirá para nos dizer se o parâmetro fornecido é aceito ou não pela máquina:

Agora... bom, vamos fazer um pequeno html para testar. Salve na mesma pasta do js que estamos escrevendo:

Funciona bem com qualquer navegador decente.

Segue listagem de código completa:

var fsm = {
	alfabeto : ['a','b'],
	estados : ['q0','q1','q2','q3','q4'],
	inicial : 'q0',
	finais : ['q4'],
	programa : {
		a : {
			q0 : "q1",
			q1 : "q2"
		},
		b : {
			q2 : "q3",
			q3 : "q4"
		} 
	},
	aceitar : function(stream){
		var atual = this.inicial;
		var i = -1;
		while(++i < stream.length){
			var next = this.programa[stream[i]][atual];
			if(next)
				atual = next;
			else
				throw new Error("Estado de saída desconhecido para {" //
				+ stream[i] + "," + atual + "}");
		}
		i = this.finais.length;
		while(i--)
			if(atual == this.finais[i])
				return true;
		return false;
	}
};

E o html:

<!DOCTYPE html>
<html>
<head>
	
	
</head>
<body>
	
Teste da máquina 
	Entrada

	
	

	
	<script type="text/javascript" src="fsm.js"></script>
	<script type="text/javascript">

	var resultado = document.getElementById("resultado");
	var entrada = document.getElementById("entrada");
	
	document.getElementById("btn").onclick=function(){
		resultado.innerHTML="";
		try{
			if(fsm.aceitar(entrada.value))
				resultado.innerHTML="Palavra aceita!";
			else
				resultado.innerHTML="Palavra recusada!";
		}catch(err){
			resultado.innerHTML="Erro ao avaliar a palavra";
		}
	};
	</script>
</body>
</html>

Fique à vontade pra melhorar esse código, o que eu mostrei aqui é uma boa demonstração mas se você for fazer seu trabalho de casa é melhor fazer direito, ;-)

Por hora é só isso, sem mais e até mais!