Module Fsa


module Fsa: sig .. end
Execução de autómatos não deterministas com (potencialmente) transições epsilon


Execução de autómatos não deterministas com (potencialmente) transições epsilon
type simbolo = char option 
O tipo simbolo representa o tipo das letras (o alfabeto - presentes nas fitas mas também nas transições). Por isso devemos considerar o alfabeto standard (aqui utilizamos o tipo char) mas também considerar a palavra/letra vazia: o epsilon.

Neste caso concreto optamos pelo tipo char option. Assim o valor Some x representa o caractere x, e o valor None representa o epsilon.

type fita = simbolo list 
a fita de entrada é simplesmente uma lista de simbolos
type estado = int 
Escolhemos representar os estados por inteiros. Em particular tentaremos respeitar o invariante seguinte sobre a representação dos estados: Se houver n estados então estes são 0 1 2 3 .. n-1.
type transicao = (estado * simbolo) * estado 
As transições q1 --a--> q2 são representadas como ((q1,a),q2) ao detrimento da representação mais natural (q1,a,q2).

Esta pequena nuance permite uma pesquisa melhorada de uma transição no conjunto das possíveis transições (de tipo hash table, em que a chave é (q1,a) e o conteudo é estado destino q2)

type maquina = transicao list * estado list * estado list 
Neste cenário, um autómato (ou máquina) é dado pela relação de transição (a listas de adjacência, ou seja a lista das transições), o conjuntos dos estados iniciais e o conjunto dos estados finais. Sendo que o alfabeto é o tipo char e conjunto dos estados se deduz automaticamente dos dados anteriores.
type memoria = estado list * fita 
As configurações da máquina (não determinista), aqui designada de memória, é simplesmente o par dos estados actualmente activos (onde se encontra no momento a execução) e o buffer ainda por processar
exception FIM of memoria
uma excepção para assinalar o fim de uma execução
val subset : 'a list -> 'a list -> bool
Duas funções simples mas naturais que codificam as noções de subconjuntos e igualdade de conjunto (sendo estes codificados como listas)
val equal : 'a list -> 'a list -> bool
val normalize : 'a list -> 'a list
As operações sobre transições, estados ou configurações podem levar a que se gere muitos duplicados nas listas que os represnetam. A função normalize de forma simples (há melhor....) mas natural permite remover estes elementos duplicados
val union : 'a list -> 'a list -> 'a list
união de dois conjuntos
val epsilon_trans_aux : 'a -> (('a * 'b option) * 'c) list * 'd * 'e -> 'c list
Dado uma máquina maq e um estado state, a função epsilon_trans_aux calcula que estados se consegue atingir a partir de state e de *uma* transição epsilon.
val epsilon_trans : 'a list -> (('a * 'b option) * 'a) list * 'c * 'd -> 'a list
Generaliza a função anterior. A função epsilon_trans calcula todos os estados atingíveis, por uma ou mais transições epsilon, a partir dos estados em lstate (lista de estado). O calculo é feito por "ponto fixo". enquanto aparecer estados novos calcula-se, mal deixe de aparecer novidades... para-se.
val select : 'a -> 'b -> (('a * 'b) * 'c) list -> 'c list
select devolve todas os estados alvo de transições que partem de est com o label simb
val next : 'a option ->
((estado * 'a option) * estado) list * 'b * 'c ->
memoria -> estado list
next calcula os estados atingíveis a partir dos estados em lesta com o simbolo simb, combinado com os estados atingíveis por transsições epsilon a partir daí.

se não houver estados atingidos, damos a indicação de que se terminou a execução

val step : memoria ->
((estado * simbolo) * estado) list * 'a * 'b ->
estado list * simbolo list
step realiza um passo de execução do autómato maq a partir da configuração memo.
val is_accepted : 'a list * 'b list -> 'c * 'd * 'a list -> bool
is_accepted é um predicado que detecta se uma configuração memo da execução do autómato maq prefigura a aceitação. Ou seja o buffer de entrada encontra-se vazio e há pelo menos um estado final na configuração
val to_fita : char -> char option
to_fita é uma função de tradução de char para simbolo. O caracter '_' é entendido como o epsilon
val em_par : 'a -> char -> 'b -> ('a * char option) * 'b
tradução para o formato transição
val char_of_string : string -> char
função utilitária simples
val leitura : unit ->
char option list * (((int * char option) * int) list * int list * int list)
Lê no formato texto o autómato por executar, e a palavra por reconhecer. A leitura devolve as estruturas correspondentes.
val print_output : 'a list * 'b list -> 'c * 'd * 'a list -> unit
a função print_output analisa a configuração final e imprime na saída standard o veredicto.
val main : unit -> unit
função principal

exemplo de entrada:

a a b a 0 1 2 0 a 0 0 b 1 0 a 3 1 a 2 2 a 3 3 a 1 3 a 2