Transition Diagram

A regular expression can also be represented graphically. The regular expression that recognizes integer and real constants (without sign) looks like this:

((di (di)*) | (di (di)* . di (di)* (E di di | )))

The edge label di for digit represents the set 0 to 9. So each edge labelled di replaces 10 edges labelled 0 to 9 with the same input and output nodes.

In the accompanying graph, the so-called , the edge labels indicate what is to be read:

As an example, we take the real constant 123.45E12

In doing so, we read the input character by character from left to right. From the node 0, upon reading the digit "1", one can reach the node 1 as well as the node 2. On subsequently reading the digit "2", there are two possible transitions: from the node 1 again to the node 1 and analogously from the node 2 again to the node 2. The same transitions take place on reading the character "3".

Now the character "." is read, and in the transition diagram, there exists no transition from node 1 under this character. So there is no path over the input into a final state via the node 1, and therefore this path is rejected. There is, however, a transition from node 2 to node 3 under the character ".". This path is continued in an analogous way.

Eventually, there exists a path from the start node 0 to an end node, here the node 7, for which the sequence of edge labels corresponds to the input word. The language accepted by the transition diagram is the set of words for which there exists such a path from the start node to an end node. In our example, a real constant was recognized correctly. This path was marked in the drawing above.


Copyright © (1999 - 2001) University of Saarland, Germany