Homework 08

This web page has an interesting implementation of a DFA:

Try reading it declaratively and then operationally.

parse(L) :- start(S), trans(S, L).

trans(X, [A|B]) :-

delta(X, A, Y),

write(X),

write(' '),

write([A|B]),

nl,

trans(Y, B).

trans(X, []) :-

final(X),

write(X),

write(' '),

write([]),

nl.

delta(0,a,1).

delta(0,b,0).

delta(1,a,1).

delta(1,b,2).

delta(2,_,2).

start(0).

final(2).

1) Write a file called nfa2.pl that implements N2 on page 51 of Sipser.

How do you handle more than one delta from the same state on the same symbol?

2) Write a file called nfa4.pl that implements N4 on page 53.

How do you handle null transitions?

3) Write a file called pda1.pl that implements M1 on page 113.

How do you handle push and pop?