Send us a comment. If a transition network is deterministic, it can be translated into a single Pop11 procedure for recognition quite straightforwardly. In this procedure, the nodes of the network give rise to labels, while transitions between nodes are implemented by gotos. Here is such a procedure for the TO-LAUGH-1 network (Figure 2.1):
define to_laugh_1(tape); vars newtape; l1: if tape matches [h ??newtape] then newtape -> tape; goto l2 else goto fail endif; l2: if tape matches [a ??newtape] then newtape -> tape; goto l3 else goto fail endif; l3: if tape matches [! ??newtape] then newtape -> tape; goto l4 elseif tape matches [h ??newtape] then newtape -> tape; goto l2 else goto fail endif; l4: if tape = [] then return(true) endif; fail: return(false) enddefine;
This procedure takes as argument a list of words representing a tape, such as
[h a h h a ! !]
and returns true or false, according to whether the sequence of words is accepted by the TO-LAUGH-1 network.
Although this approach works, it uses a pathological programming
style and the resulting program is almost completely unstructured.
Apart from the fact that such a simple method of translation will not
work when the network is non-deterministic, there are other reasons why this
approach is not to be preferred:
First of all, the size of the code that has
to be written is significantly greater than that of the original network
specification.
Secondly, the code will only support one task - recognition.
If we wish to use the network for some other purpose, such as
random generation, we must produce completely new code. So our
approach here will be, instead of representing a network procedurally, to
represent a network declaratively as a Pop11 data structure that can be
examined and manipulated. We will then write general-purpose recognition and
generation programs that will work on any network represented as a
data structure in the approved way.
Send us a comment.