автоматы в ocaml

Question

Я немного новичок в OCaml. Я хочу реализовать алгоритм построения продукта для автоматов в ocaml. Я запутался, как изобразить автоматы в ocaml. Кто-нибудь может мне помочь?

Answer 1

Чистое представление для конечного детерминированного автомата было бы:

type ('state,'letter) automaton = {
  initial    : 'state ;
  final      : 'state -> bool ;
  transition : 'letter -> 'state -> 'state ;
}

Например, автомат, который определяет, содержит ли слово нечетное число 'a', мог бы быть представлен следующим образом:

let odd = {
  initial    = `even ; 
  final      = (function `odd -> true | _ -> false) ;
  transition = (function 
    | 'a' -> (function `even -> `odd | `odd -> `even)
    |  _  -> (fun state -> state))
}

Другим примером является автоматизация, которая принимает только строку "bbb" (да, они взяты из этого онлайн-раздаточного материала ):

let bbb = {
  initial = `b0 ;
  final   = (function `b3 -> true | _ -> false) ;
  transition = (function 
    | 'b' -> (function `b0 -> `b1 | `b1 -> `b2 | `b2 -> `b3 | _ -> `fail)
    |  _  -> (fun _ -> `fail))
}

Автоматизированный продукт описан математическикак использование декартового произведения наборов состояний в качестве новых наборов и естественных расширений конечных функций и функций перехода над этим набором:

let product a b = {
  initial = (a.initial, b.initial) ;
  final   = (fun (x,y) -> a.final x && b.final y) ;
  transition = (fun c (x,y) -> (a.transition c x, b.transition c y)
}

Этот продукт-автомат вычисляет пересечение двух языков.Вы также можете использовать || вместо && для реализации объединения двух языков.