Prolog Regexp

% Infix operators for shorthand
:- op(1000,yfx,•).
:- op(1200,yfx,∪).
:- op(1100,yfx,∩).
:- op( 900, xf,∗).

% Notes on names:
% P     Pattern
% I     Input
% Subscripts ᵢ and ⱼ are used to differentiate two things of the same
%   type, e.g., two patterns, or two inputs.
% The subscript ᵨ denotes that the variable is an array.

% Epsilon matches empty
regex(ε,[]).

% Concatenation
regex(•(Pᵢ,Pⱼ),Iᵨ)
 :- append(Iᵢ,Iⱼ,Iᵨ)
  , regex(Pᵢ,Iᵢ)
  , regex(Pⱼ,Iⱼ).

% Union
regex(∪(Pᵢ,Pⱼ),Iᵨ)
 :- regex(Pᵢ,Iᵨ)
  ; regex(Pⱼ,Iᵨ).

% Intersection
regex(∩(Pᵢ,Pⱼ),Iᵨ)
 :- regex(Pᵢ,Iᵨ)
  , regex(Pⱼ,Iᵨ).

% Kleene Star
regex(∗(_),[]).
regex(∗(Pᵢ),Iᵨ)
 :- append(Iᵢ,Iⱼ,Iᵨ)
  , regex(Pᵢ,Iᵢ)
  , regex(*(Pᵢ),Iⱼ).

regex(P,[P])
 :- atom(P).