Module Dfsa (.ml)

module Dfsa: sig .. end

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 : simbolo -> estado -> maquina -> estado

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 (situação processada pela função step).

val step : memoria -> maquina -> memoria

step realiza um passo de execução do autómato maq a partir da configuração memo.

val is_accepted : memoria -> maquina -> 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 -> fita * maquina

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

val print_output : memoria -> maquina -> 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