Module Fsa (.ml)

module Fsa: sig .. end

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