Module Dfsa


module Dfsa: sig .. end
Execução de autómatos deterministas


Execução de autómatos deterministas
type simbolo = char 
O tipo simbolo representa o tipo das letras (o alfabeto - presentes nas fitas mas também nas transições). Aqui fixamos o tipo char como sendo o alfabeto usado nestes autómatos.
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 * 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* estado inicial e o conjunto dos estados finais. Sendo que o alfabeto e conjunto dos estados se deduz automaticamente dos dados anteriores.
type memoria = estado * fita 
As configurações da máquina (determinista), aqui designada de memória, é simplesmente o par *do* estado actualmente activo (onde a máquina se encontra no momento a execução) e o buffer que resta ainda por processar.
exception FIM of memoria
uma excepção para assinalar o fim de uma execução
val next : 'a -> ((estado * 'a) * 'b) list * 'c * 'd -> memoria -> 'b
next calcula o próximo estado, ou seja o estado q destino da transição esta---simb--->q, se esta transição existir. Senão (i.e. a excepção Not_found foi lançada) esta situação configura o fim da execução.
val step : memoria ->
((estado * simbolo) * 'a) list * 'b * 'c -> 'a * simbolo list
step realiza um passo de execução do autómato maq a partir da configuração memo.
val is_accepted : 'a * '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 em_par : 'a -> 'b -> 'c -> ('a * 'b) * 'c
funções utilitárias simples
val char_of_string : string -> char
val leitura : unit -> char list * (((int * char) * int) list * int * int list)
Lê no formato texto a palavra por reconhecer e o autómato por executar. A leitura devolve as estruturas correspondentes.
val print_output : 'a * '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

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