Module Fsa_set (.ml)

module Fsa_set: sig .. end

Execução de autómatos não deterministas com transições codificadas como tabelas de Hash para conjuntos de estados

compilação: ocamlopt fsa_set.ml -o ndfa

versão >=4.07

documentação: ocamldoc -hide-warnings -html -charset utf8 -short-functors -stars -keep-code -colorize-code -impl fsa_set.ml

Estruturas de dados

type simbolo = char option

simbolo é o tipo para o alfabeto considerado, aumentado do símbolo "epsilon". O símbolo "epsilon" tem por representação o valor None e o caracter c tem por representação Some c

type fita = simbolo list

a fita de entrada é representada por uma lista de símbolos, de tipo fita

module Estados: sig .. end

Estados: módulo para a representações dos estados de um autómato.

module Sestado: Stdlib.Set.Make(Estados)

Sestado: módulo para conjuntos de estados

type estado = Estados.t

tipo dos estados, como abreviatura do tipo Estados.t

type estados = Sestado.t

tipo dos conjuntos de estados, como abreviatura do tipo Sestado.t

type transicoes = (estado * simbolo, estados) Stdlib.Hashtbl.t

transicoes: tipo das transições. Codificado como uma hashtable de (estado*simbolo) para conjuntos de estados (por causa do não-determinismo)

type maquina = transicoes * estados * estados

maquina: tipo dos autómatos não deterministas. Um autómato é definido como o tuplo (transições, estados iniciais, estados finais)

type configuracao = estados * fita

configuracao: tipo das configurações. Uma configuração é um par

Leitura dos dados

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 triplo : '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 read_to_list : (string -> 'a) -> 'a list

read_to_set lê uma linha de inteiros e devolve na forma de uma lista de inteiros

val read_to_set : (string -> Sestado.elt) -> Sestado.t

read_to_set lê uma linha de inteiros e devolve na forma de um conjunto de inteiros

val read_transition : unit -> transicoes

read_transition lê transições linha a linha até ao fim de ficheiro. Formata as transições lidas para o tipo transicoes

val leitura : unit ->
       char option list *
       (transicoes * Sestado.t * Sestado.t)

leitura lê no formato texto o autómato por executar, e a palavra por reconhecer. A leitura devolve as estruturas correspondentes.

Execução

exception FIM of configuracao

execução que permite assinalar o fim de uma execução, com o registo da respectiva configuração final

val reach : maquina -> estado -> simbolo -> estados

reach calcula que estados são alvo de transições directas que partem do estado state com rótulo ch no autómato maquina

val reach_states : maquina -> estados -> simbolo -> Sestado.t

reach_states calcula que estados são alvo de transições directas que partem do conjunto de estados states com rótulo ch no autómato maquina

val reach_star_aux : maquina ->
       estados -> estados -> simbolo -> estados

reach_star_aux é função (recursiva) auxiliar da função reach_star e calcula que estados são alvo de transições directas e indirectas que partem do conjunto de estados todo com rótulo ch no autómato maquina. Os estados já considerados encontram-se em final, nunca é considerado estados de final quando são processados os estados de todo -- os estados de todo são realmente os estados que restam ainda processar. Após estarem devidamente processados, passam para final Um dos invariantes mantidos é que os estados de final são todos atingíveis por ch a partir de um caminho que parte dos estados de todo da chamada inicial.

val reach_star : maquina -> estados -> simbolo -> estados

reach_star calcula que estados são alvo de transições directas e indirectas (i.e. uma ou mais) que partem do conjunto de estados states com rótulo ch no autómato maquina

val reach_epsilon : maquina -> estados -> estados

reach_epsilon devolve o conjunto de estados para os quais existe um caminho "epsilon" que parte dos estados de states -- i.e. os estados atingíveis por epsilon partindo de states

val next : transicoes * estados * estados ->
       estados * fita -> simbolo -> estados

next calcula os estados atingíveis a partir dos estados em states com o simbolo simb, combinado com os estados atingíveis por transições epsilon a partir daí. se não houver estados atingidos, damos a indicação de que se terminou a execução

val step : transicoes * estados * estados ->
       estados * fita -> estados * simbolo list

step realiza um passo de execução do autómato maquina a partir da configuração config. se não resta elementos na fita de entrada então damos a indicação de que terminou a execução, senão devolvemos a configuração seguinte (considerando o autómato maquina e a configuração config=(states, a.w):

(states, a.w) |-' (states', w)

em que states' = (next maquina config)

val step_star : maquina -> configuracao -> 'a

step_star é a função de execução principal. executa repetidamente step a partir de uma dada configuração. Espera-se que esta seja invocada com a configuração inicial (estendida com todos os estados atingíveis com transições epsilon dos estados iniciais)

val is_accepted : maquina -> Sestado.t * 'a list -> bool

is_accepted é um predicado que detecta se uma configuração da execução do autómato (ambos passados em parâmetro) prefigura a aceitação. Ou seja o buffer de entrada encontra-se vazio e há pelo menos um estado final na configuração

val print_output : maquina -> configuracao -> unit

a função print_output analisa a configuração final e imprime na saída standard o veredicto.

val main : unit -> unit

main função principal

epílogo

Exemplo de entrada:

Resposta:

YES