open List
open Str
open Scanf
open Printf

(**

Execução de autómatos deterministas

*)




(**

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 simbolo = char 


(** a fita de entrada é simplesmente uma lista de simbolos *)

type fita =  simbolo list

(**

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 estado = int 

(**

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 transicao =  ((estado*simbolo)*estado)

(**

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 maquina =  (transicao list * estado * estado list)

(**

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.

*)

 
type memoria = (estado * fita)

(** uma excepção para assinalar o fim de uma execução *)

exception FIM of memoria



(**

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).

*)


let next (simb:simbolo)  (aqui:estado) (maq:maquina)= 
    let transicoes,b,c = maq in
    (assoc (aqui,simb) transicoes)




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

let step (memo:memoria) (maq:maquina) = 
  let (aqui, restante) = memo in
  
  (** se o buffer de entrada for vazio, então acabou, senão tratamos do primeiro caracter do buffer. Ou seja, vamos ver que novo estado atingimos com este caracter a partir do estado actualmente activo (onde a execução actualmente se encontra, o estado aqui). Chamanos aqui a função next que trata deste cálculo. *)

  match restante with
      [] ->  raise (FIM memo)
    | el::li ->
       try  
         (((next el aqui maq),(li:fita)) : memoria) 
       with Not_found -> raise (FIM memo)

(** 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 *)

let is_accepted (memo:memoria) (maq:maquina) =
  let (aqui, restante) = memo in
  let (trans,init,accept)= maq in
  (mem aqui accept)&&(restante=[])

(** funções utilitárias simples*)

let em_par a b c =  ((a, b),c);;

let char_of_string s = s.[0];;

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

let leitura () =
  let dados = map (fun x -> char_of_string x) 
   (Str.split (Str.regexp "[ \t]+")  (read_line ())) in
  let initl = read_int () in
  let finl = map (fun x -> int_of_string x) 
    (Str.split (Str.regexp "[ \t]+")  (read_line ()))  in
  let input = ref [] in
    try
      while (true) do
        input:= (scanf " %d %c %d " em_par)::!input
      done; (dados,(!input,initl,finl))
    with _ -> ((dados:fita),((!input,initl,finl):maquina));;


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

let print_output (memo:memoria) (maq:maquina)= 
    if (is_accepted memo maq) 
    then printf "YES\n"
    else printf"NO\n"


let main () =
  let dados,(maq:maquina) = leitura () in
  let (a,b,c) = maq in 
    try
      let memor = ref (b,dados)  in
        
        (** Enquanto houver passos de execução por realizar, executar. A excepção FIM é lançada para assinalaro fim da execução. *)

      while true do
        memor := (step !memor maq)
      done
    with
        FIM x -> print_output x maq
;;

main ();;

(** 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

*)