[Overview] [Previous] [Next]

Example

Consider the grammar G = ({S, A, B}, {a, b}, S, P), where
P = {Sgoes toa, Sgoes toaAB, Agoes toaA, Agoes toa, Bgoes tobB, Bgoes tob}.

These productions can be turned into transition functions by rearranging the components:
rearrangement

This yields the following table:

(start) delta(q0, empty string, z) goes to {(q1, Sz)}
Sgoes toa, delta(q1, a, S)goes to{(q1, empty string)}
Sgoes toaAB, delta(q1, a, S)goes to{(q1, AB)}
Agoes toaA, delta(q1, a, A)goes to{(q1, A)}
Agoes toa, delta(q1, a, A)goes to{(q1, empty string)}
Bgoes tobB, delta(q1, b, B)goes to{(q1, B)}
Bgoes tob delta(q1, b, B)goes to{(q1, empty string)}
(finish) delta(q1, empty string, z) goes to {(qf, z)}

For example, the derivation

S directly derives aAB directly derives aaB directly derives aabB directly derives aabb
maps into the sequence of moves
(q0, aabb, z) move to (q1, aabb, Sz) move to (q1, abb, ABz) move to (q1, bb, Bz)
move to (q1, b, Bz) move to (q1, empty string, z) move to (q2, empty string, empty string)


Copyright 1996 by David Matuszek
Last modified Mar 17, 1996