I need to get the delta function of a non-deterministic pushdown automaton from a context-free grammar in DCG form, and the algorithm for doing this is very simple:
For every rule A --> B in the grammar, add a transition [q1, lambda, A] --> [B] to the delta function.
For every rule E --> c in the grammar, add a transition [q1, c, c] --> [lambda] to the delta function.
Add the transitions [q0, lambda, z0] --> [q1, S*z0] and [q1, lambda, z0] --> [q2, z0] to the delta function.
Every uppercase letter is a non-terminal symbol, and every lowercase letter is a terminal symbol. lambda is the empty string, S is the initial symbol of the grammar, * is the concatenation operator and z0 is the symbol on the top of the stack.
This means the grammar
S --> A*b | B | y
A --> w*x | x
B --> A*b
generates a pushdown automaton with the delta function
[q0, lambda, z0] --> [q1, S*z0]
[q1, lambda, S] --> [q1, A*b]
[q1, lambda, S] --> [q1, B]
[q1, lambda, S] --> [q1, y]
[q1, lambda, A] --> [q1, w*x]
[q1, lambda, A] --> [q1, x]
[q1, lambda, B] --> [q1, A*b]
[q1, b, b] --> [q1, lambda]
[q1, w, w] --> [q1, lambda]
[q1, x, x] --> [q1, lambda]
[q1, y, y] --> [q1, lambda]
[q1, lambda, z0] --> [q2, z0]
I have to implement this algorithm in Prolog (getting a grammar from user and returning the delta function) and I'm confused because this is my first time using a logic programming language.
I thought I could maybe translate the grammar into its predicate form and then "iterating" over all the predicates, and somehow adding the already "traversed" predicates to a list, so I can process this list and return the delta function. But I think this is some sort of really complicated imperative way of doing things and using Prolog for this would be pointless.
Maybe there's a more elegant solution for this problem, so I'd like to know if such solution exists.
Here a possible coding
g2nfa(Grammar, Delta) :-
maplist(transitions, Grammar, DeltaT),
append(DeltaT, DeltaF),
Initial = (q0, lambda, z0 --> q1, 'S'*z0),
Final = (q1, lambda, z0 --> q2, z0),
append([[Initial], DeltaF, [Final]], Delta).
transitions(Sym --> Alternatives, Transitions) :-
phrase(transition(Sym, Alternatives), Transitions).
transition(Sym, A|As) --> state(Sym, A), !, transition(Sym, As).
transition(Sym, A) --> state(Sym, A).
state(Sym, A) --> [(q1, lambda, Sym --> q1, A)].
test :-
g2nfa([( 'S' --> 'A'*b | 'B' | y ),
( 'A' --> w*x | x ),
( 'B' --> 'A'*b )
], T), maplist(writeln, T).
that seems to satisfy your requirements
?- test.
q0,lambda,z0-->q1,S*z0
q1,lambda,S-->q1,A*b
q1,lambda,S-->q1,B
q1,lambda,S-->q1,y
q1,lambda,A-->q1,w*x
q1,lambda,A-->q1,x
q1,lambda,B-->q1,A*b
q1,lambda,z0-->q2,z0
true.
so you can work out the syntactic details. Note that the second rewrite rule (For every rule E --> c in the grammar, add a transition [q1, c, c] --> [lambda] to the delta function.) has not been applied in your sample.