Автоматы в окамле

Ответ 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)
}

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