README.md

PostgreSQL Deterministic (non-complete) Finite State Automaton

• Provides a run aggregate to execute the automaton over rows of symbols, given an initial state.
• Provides an accepts function that tells wether or not a given string is accepted, given an initial state

The state of id=0 is a sink and shouldn't be modified. Algorithms rely on it when a transition is undefined.

What did I learn

• Custom aggregate definition
• coalesce, unnest

License

CC-BY-4.0 OR MIT OR Apache-2.0 (spdx)

dfsa_run.sql

insert into states values (1, false), (2, true);
insert into transitions values
  (1, 'a', 1),
  (1, 'b', 2)
;

select accepts(1, 'aaaab');
select accepts(1, 'b');
select accepts(1, 'aaaba');
select accepts(1, 'aaaaa');

dfsa_schema.sql

create table states (
  id integer not null,
  acceptor bool not null default false,
  
  primary key (id)
);

create table transitions (
  f integer not null references states,
  symbol char not null,
  t integer not null references states,

  primary key (f, symbol)
);

insert into states (id, acceptor) values (0, false);

create function transition(f_s int, f_init int, f_symbol char)
returns int
stable
as 'select coalesce((select t from transitions where f = coalesce(f_s, f_init) and symbol = f_symbol limit 1), 0);' language sql;

create aggregate run(f_init int, f_symbol char) (
  sfunc = transition,
  stype = int
);

create function accepts(init integer, string text) returns bool as 'select acceptor from states where id = (select run(init, symbol) from unnest(string_to_array(string, null)::char[]) as symbol);' language sql;