I have coded the below program in prolog to almost work perfectly. I am having trouble including epsilon transitions into the different states. I have bolded the functions below that I am capable of editing for the project. As of now, the program works correctly for any input not including an epsilon. Demo4 is a NFA that should accept the epsilon state.

%%%% simulates a non-deterministic finite state

%%%% automaton.

%%% ================ representations

%%% input character string is represented as a list of symbols, e.g., [a, b, a, c]

%%% A state is represented using the functor state, whuch takes 3 arguments:

%%%  – name, a symbol: the name of this state

%%%  – transition list: a list of transition structures

%%%  – accepting: the symbol yes or no

%%% a transition structure is represented using the functor transition,

%%% which takes 2 arguments:

%%% – character, which is a character or epsilon

%%% – name of resulting state.

%%% There is no special structure or functor for an fsa. It is just represented as a list of state structures, the

%%% first state structure in the list is the starting state of the fsa

%%% e.g., this fsa:

%  ___ 0 ___  0

% |  |  1|  |

% -> even <—————-odd <-/

%         ^ |

%   —————-| | 1

%  1           V

% State even is the foo ————> bar

%  start state            epsilon

% Even and bar are

%  accepting states.

%

%%% is represented as follows:

%%%  [state(even, [transition(0, even), transition(1, odd)], yes),

%%%  state(odd,[transition(1, foo), transition(0, odd), transition(1, even)], no),

%%%  state(foo, [transition(epsilon, bar)], no)

%%%  state(bar, [ ], yes)]

%%% ================ predicates

%%% state_struct(+Name, +States, -State_struct)

%%%  Name is a state name,

%%%  States a list of state structures, and

%%%  State_Struct the state structure from States with name Name

%define state_struct here

state_struct(Name, States, state(Name, Transitions, Accept)):- member(state(Name, Transitions, Accept), States).

%%% next_state_name(+State_struct, +Characters, -Next_name, -Next_chars)

%%% find (the name of) a next state to transition to

%%%  State_struct is the current state,

%%%  Characters is the list of characters currently left in the input,

%%%  Next_name is the name of the next state, and Next_chars is the

%%%   remaining list of input chars

% %% next_state_name(state(_, Transitions, _), [_ | Char_tail], Name2,Char_tail):- member(transition(Char_tail,Name2), Transitions).

%define next_state_name here

next_state_name(state(_, Transitions, _), [Char_head|Char_tail], Next_name, Char_tail) :-

member(transition(Char_head, Next_name), Transitions), member(transition(epsilon, Next_name), Transitions).

% accepts(+State_struct, +Fsa, +Chars) true if Fsa accepts character% string Chars when starting from the state represented by State_struct

%accepts(state(_,_,yes),_, []).

% accepts(state(Name, Transitions, Accept), States,

% [Char_head|Char_tail]):- next_state_name(state(Name, Transitions,

% Accept), [Char_head | Char_tail], Name2, Char_tail),

% state_struct(Name2, States, Next_state), accepts(Next_state, States,

% Char_tail).

% accepts(state(Name, [State1 | State2], Accept), States, [Char_head|Char_tail]):-

%  next_state_name(state(Name, [State1 | State2],

%  Accept),[Char_head|Char_tail], Name2, Char_tail),

%  state_struct(Name2,States, Next_state),

%  accepts(Next_state, States, Char_tail).

%define accepts here

accepts(state(_, _, yes), _, [ ]).

accepts(state(Name, Transitions, Accept), States, [Char_head|Char_tail]) :-

next_state_name(state(Name, Transitions, Accept), [Char_head|Char_tail], Next_name, Char_tail),

state_struct(Next_name, States, Next_state),

accepts(Next_state, States, Char_tail).

%%% run(Fsa, Chars) Fsa is a list of state stuctures representing

%%% a Fsa (so that the first state in the list is the start state of

%%% the fsa), Chars is a list of symbols and numbers representing

%%% the input to the fsa. run succeeds if and only if the fsa

%%% would accept the sequence of characters

run([State1 | States], Chars):- accepts(State1,[State1 | States], Chars).

% demo1 and demo2 demonstrate calls to run. They each specify a

% automaton and allow you to run that automaton with different input

% strings, by calling, e.g., demo1([1, 0]).

%

% demo1 and demo2 are here to show you how to call your code. They

% are NOT intended to provide sufficient test data for your code. Among

% other things, they do not test epsilon transitions.

% demo1 shows a deterministic finite state automaton.

% demo1([ ]) should return true, as should demo1([1,1]), demo1([0,1,1]),

%   demo1([1,1,0,0,1,0,1]), etc (any string with an even number of 1’s)

%   demo1([1]) should return false, as should demo1([1,0,1,1]) as should any

%   string with an odd number of 1’s

demo1(Chars):- run([state(even,[ transition(0, even),transition(1, odd)], yes),

          state(odd,[transition(0, odd), transition(1, even)], no)],

  Chars).

% demo2 shows non-determinism: there are transitions from state odd

%  both to even and to other for the character 1. both demo2([1,1,0]). and demo2([1,1,2]).

%  should return true.

demo2(Chars):- run([state(even,[ transition(0, even),transition(1, odd)], yes),

          state(odd,[transition(1, even), transition(1, other), transition(0, odd)], no),

  state(other,[transition(2, otherb)],no),

  state(otherb,[ ], yes)],

  Chars).

demo3(Chars):- run([state(even, [ transition(0,even),transition(1,even),transition(1,odd)], no),

  state(odd, [transition(1,odd)], yes)],

   Chars).

demo4(Chars):- run([state(even, [transition(0,even),transition(1,odd)],yes),

  state(odd, [transition(0,odd),transition(1,even),transition(1,foo)],no),

  state(foo, [transition(epsilon, bar)], no),

  state(bar, [], yes)],

  Chars).