% PFLAP: Prolog Finite Automata and Language Analysis Program
% Author: Robert Keller, Harvey Mudd College
% Installment 2  (includes DFA, NFA, PDA by empty-stack)

% Usage: SWI-Prolog is recommended. On knuth this would be
%     pl -f pflapTest.pl
% Copy pflap.pl to your directory
% Edit in your own examples into pflapTest.pl

:- ensure_loaded(pflap).

% A DFA (Deterministic Finite-State Acceptor) is given by a term
%
% dfa(Q, A, q0, F, T) where
%
% Q is the list of states
% A is the input alphabet
% qo is the start state
% F is the list of accepting or "final" states
% T is a list of transitions: triples, of the form (pre-state, input-symbol, post-state)

% Procedures for a DFA:
%
%     testDFA(DFA, [... strings ...]).
%        tests the DFA for acceptance on strings in the given list
%
%     showAcceptedInputsDFA(DFA, Steps).
%        shows all string accepted by DFA in Steps or fewer steps.
%
%     minimizeDFA(DFA, Min)
%        minimizes states of a DFA, resulting in Min.
%
%     showDFA(DFA)
%        shows the details of DFA.

% An NFA (Nondeterministic Finite-State Acceptor) is given by a term
%
% nfa(Q, A, S, F, T) where
%
% Q is the list of states
% A is the input alphabet
% S is set of initial states
% F is the list of accepting or "final" states
% T is a list of transitions: triples, of the form (pre-state, input-symbol, post-state)

% Procedures for an NFA:
%
%     testNFA(NFA, [... strings ...]).
%        tests the NFA for acceptance on strings in the given list.
%
%     showAcceptedInputsNFA(NFA, Steps).
%        shows all strings accepted by NFA in Steps or fewer steps.
%
%     showNFA(NFA)
%        shows the details of NFA.


% A PDA ((non-deterministic) Pushdown Acceptor) is given by a term
%
% pda(Q, Z, s0, A, q0, F, T) where
%
% Q is the list of control states
% Z is the stack alphabet
% S is the initial stack symbol
% A is the input alphabet
% q0 is the initial control state
% F is the list of accepting or "final" states
% T is a list of transitions: 5-tuples, of the form 
%     (pop, pre-state, input-symbol, push, post-state)
% where pop is a symbol in the stack alphabet that is popped off when this transition occurs
% pre-state is the control state enabling this transition
% input-symbol is either in the input alphabet or is epsilon (here represented as [])
% push is a sequence of symbols that are pushed when this transition occurs
% post-state is the control state following this transition

% Procedures for PDA:
%
% testPDAES(PDA, [... strings ...]).
%    Tests PDA on strings in the given list, with acceptance by empty-stack (ES).
%
% showAcceptedInputsPDAES(PDA, Steps).
%    Shows all strings accepted by PDA by empty-stack in Steps or fewer steps.
%
%     showPDA(PDA)
%        shows the details of PDA.


% Some examples to be tested

% Example DFA

example01(
  dfa([q0, q1, q2], [a, b], q0, [q2],
      [(q0, a, q0),
       (q0, b, q1),
       (q1, a, q0),
       (q1, b, q2),
       (q2, a, q0),
       (q2, b, q1)])
         ).

test01 :- nl, example01(DFA), 
    testDFA(DFA, [aabb, abba]),
    showAcceptedInputsDFA(DFA, 5).


% Example DFA

example02(
  dfa([q0, q1, q2], [0, 1], q0, [q0],
      [(q0, 0, q0),
       (q0, 1, q1),
       (q1, 0, q2),
       (q1, 1, q0),
       (q2, 0, q1),
       (q2, 1, q2)])
         ).

test02 :- example02(DFA), showAcceptedInputsDFA(DFA, 5).


% Example NFA

example03(
  nfa([q0, q1, q2], [0, 1], [q0], [q0, q1],
      [(q0, 0, q0),
       (q0, 0, q1),
       (q0, 1, q1),
       (q1, 0, q2),
       (q1, 1, q0),
       (q1, 1, q1),
       (q2, 0, q1),
       (q2, 1, q2)])
         ).

test03 :- example03(NFA), 
    testNFA(NFA, 
        ['10',
         '010']),
    showAcceptedInputsNFA(NFA, 5).


% Example NFA with epsilon transition

example04(
  nfa([q0, q1, q2], [0, 1], [q0], [q2],
      [(q0, 0, q0),
       (q0, [], q1), % epsilon transition
       (q1, 0, q0),
       (q1, 1, q2)])
         ).

test04 :- example04(NFA), 
    testNFA(NFA, [
       '01',
       '00']),
    showAcceptedInputsNFA(NFA, 10).


% Example NFA with multiple start states

example05(
  nfa([q0, q1, q2], [0, 1], [q0, q1], [q2],
      [(q0, 0, q2),
       (q1, 1, q2),
       (q1, 1, q1)])
         ).

test05 :- example05(NFA), 
    testNFA(NFA, [
        '01',
        '11']),
    showAcceptedInputsNFA(NFA, 10).


% Example NFA only accepting the empty sequence

example06(
  nfa([q0, q1], [0, 1], [q0], [q0],
      [(q0, 0, q1),
       (q0, 1, q1)])
         ).

test06 :- example06(NFA), showAcceptedInputsNFA(NFA, 10).


example07(
  nfa([s, z, a, b, c], [a, b], [s], [c, z],
      [(s, a, z),
       (s, [], a),
       (a, a, a),
       (a, b, b),
       (b, a, c),
       (b, b, a),
       (b, b, b),
       (c, a, a)])
        ).

test07 :- example07(NFA), showAcceptedInputsNFA(NFA, 10).

% Example pda accepting by empty-stack

example08(
      pda([q0], [s, r, a, b, '[', ']', ','], s,
                [a, b, '[', ']', ','],
                q0, [],
          [(s,   q0, [],  ['[', ']'],  q0),
           (s,   q0, [],  ['[', s, r], q0),
           (s,   q0, [],  [a],         q0),
           (s,   q0, [],  [b],         q0),
           (r,   q0, [],  [']'],       q0),
           (r,   q0, [],  [',', s, r], q0),
           (a,   q0, a,   [],          q0),
           (b,   q0, b,   [],          q0),
           ('[', q0, '[', [],          q0),
           (']', q0, ']', [],          q0),
           (',', q0, ',', [],          q0)
          ])).

test08 :- example08(PDA), 
  testPDAES(PDA,
    [
    a,
    ']',
    '[',
    '[a]',
    '[a,b]',
    '[a,[b]]',
    '[a,[b]',
    '[a,[b,a]]'
    ]),
   showAcceptedInputsPDAES(PDA, 15).

% DFA to minimize

example09(
  dfa([q0, q1, q2], [a, b], q0, [q1],
      [(q0, a, q0),
       (q0, b, q1),
       (q1, a, q0),
       (q1, b, q1),
       (q2, a, q0),
       (q2, b, q1)])
         ).

test09 :- nl, example09(DFA), 
    showDFA(DFA),
    minimizeDFA(DFA, Min),    
    showDFA(Min).


% Even-length non-empty palindrome example

example10(
      pda([q0], [s, a, b], s,
                [a, b],
                q0, [],
          [(s, q0, a,   [a, s],  q0),
           (s, q0, b,   [b, s],  q0),
           (a, q0, a,   [a, a],  q0),
           (a, q0, b,   [b, a],  q0),
           (b, q0, a,   [a, b],  q0),
           (b, q0, b,   [b, b],  q0),
           (a, q0, [],  [a],  q1),
           (b, q0, [],  [b],  q1),
           (a, q1, a,   [],  q1),
           (b, q1, b,   [],  q1),
           (s, q1, [],  [],  q1)
          ])).

test10 :- example10(PDA), 
   testPDAES(PDA, [abba, abbb]),
   showAcceptedInputsPDAES(PDA, 9).


% Even-length non-empty palindrome example, with 1 state
% This takes one more step than the previous pda, due to
% the initialization construction

example11(
      pda([q0], [s, a, b], x,
                [a, b],
                u, [],
          [(x, u, [], [(q0, s, q0)], u),
           (x, u, [], [(q0, s, q1)], u),

           ((q0, s, q0), u, a, [(q0, a, q0), (q0, s, q0)], u),
           ((q0, s, q1), u, a, [(q0, a, q0), (q0, s, q1)], u),
           ((q0, s, q0), u, a, [(q0, a, q1), (q1, s, q0)], u),
           ((q0, s, q1), u, a, [(q0, a, q1), (q1, s, q1)], u),

           ((q0, s, q0), u, b, [(q0, b, q0), (q0, s, q0)], u),
           ((q0, s, q1), u, b, [(q0, b, q0), (q0, s, q1)], u),
           ((q0, s, q0), u, b, [(q0, b, q1), (q1, s, q0)], u),
           ((q0, s, q1), u, b, [(q0, b, q1), (q1, s, q1)], u),

           ((q0, a, q0), u, a, [(q0, a, q0), (q0, a, q0)], u),
           ((q0, a, q1), u, a, [(q0, a, q0), (q0, a, q1)], u),
           ((q0, a, q0), u, a, [(q0, a, q1), (q1, a, q0)], u),
           ((q0, a, q1), u, a, [(q0, a, q1), (q1, a, q1)], u),

           ((q0, a, q0), u, b, [(q0, b, q0), (q0, a, q0)], u),
           ((q0, a, q1), u, b, [(q0, b, q0), (q0, a, q1)], u),
           ((q0, a, q0), u, b, [(q0, b, q1), (q1, a, q0)], u),
           ((q0, a, q1), u, b, [(q0, b, q1), (q1, a, q1)], u),

           ((q0, b, q0), u, a, [(q0, a, q0), (q0, b, q0)], u),
           ((q0, b, q1), u, a, [(q0, a, q0), (q0, b, q1)], u),
           ((q0, b, q0), u, a, [(q0, a, q1), (q1, b, q0)], u),
           ((q0, b, q1), u, a, [(q0, a, q1), (q1, b, q1)], u),

           ((q0, b, q0), u, b, [(q0, b, q0), (q0, b, q0)], u),
           ((q0, b, q1), u, b, [(q0, b, q0), (q0, b, q1)], u),
           ((q0, b, q0), u, b, [(q0, b, q1), (q1, b, q0)], u),
           ((q0, b, q1), u, b, [(q0, b, q1), (q1, b, q1)], u),

           ((q0, a, q0), u, [], [(q1, a, q0)], u),
           ((q0, a, q1), u, [], [(q1, a, q1)], u),

           ((q0, b, q0), u, [], [(q1, b, q0)], u),
           ((q0, b, q1), u, [], [(q1, b, q1)], u),

           ((q1, a, q1), u, a, [], u),
           ((q1, b, q1), u, b, [], u),

           ((q1, s, q1), u, [], [], u)
          ])).

test11 :- example11(PDA), 
   testPDAES(PDA, [abba, abbb]),
   showAcceptedInputsPDAES(PDA, 10).

example12(
    pda([a, b], [s, 0], s, [0, 1], a, [], 
      [
      (s, a, [], [], a),
      (s, a, 0,  [0, s], a),
      (0, a, 0,  [0, 0], a),
      (0, a, 1,  [], b),
      (0, b, 1,  [], b),  	% was (0, b, 0,  [], b),
      (s, b, [], [], b)
      ])).

test12 :- example12(PDA), 
   showAcceptedInputsPDAES(PDA, 10).

example13(
    pda([u],
        [x, (a,s,a), (a,0,a), (a,0,b), (b,0,b), (b,s,b)],
        x,
        [0, 1],
        u,
        [],                
      [
      % initial transitions

      (x, u, [], [(a,s,a)], u),
      (x, u, [], [(a,s,b)], u),

      % (s, a, [], [], a) transitions

      ((a,s,a), u, [], [], u),

      % (s, a, 0,  [0, s], a) transitions

      ((a,s,a), u, 0, [(a,0,a), (a,s,a)], u),
      ((a,s,a), u, 0, [(a,0,b), (b,s,a)], u),
      ((a,s,b), u, 0, [(a,0,a), (a,s,b)], u),
      ((a,s,b), u, 0, [(a,0,b), (b,s,b)], u),

      % (0, a, 0,  [0, 0], a) transitions

      ((a,0,a), u, 0, [(a,0,a), (a,0,a)], u),
      ((a,0,a), u, 0, [(a,0,b), (b,0,a)], u),
      ((a,0,b), u, 0, [(a,0,a), (a,0,b)], u),
      ((a,0,b), u, 0, [(a,0,b), (b,0,b)], u),

      % (0, a, 1,  [], b) transitions

      ((a,0,b), u, 1, [], u),

      % (0, b, 0,  [], b) transitions

      ((b,0,b), u, 1, [], u),

      % (s, b, [], [], b) transitions

      ((b,s,b), u, [], [], u)
      ])).

test13 :- example13(PDA), 
   showAcceptedInputsPDAES(PDA, 10).

% Master test

test :- test01, 
        test02, 
        test03, 
        test04, 
        test05, 
        test06,
        test07,
        test08,
        test09,
        test10,
        test11,
        test12,
        test13.