We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
You are on page 1/ 1
If you block the paths of a graph for or aft by a graph that has no paths , there
won't be any paths,
REDUCTION PROCEDURE:
+ REDUCTION PROCEDURE ALGORITHM:
This section presents a reduction procedure for converting a flowgraph whose
links are labeled with names into a path expression that denotes the set of all
entry/exit paths in that flowgraph. The procedure is a node-by-node removal
algorithm,
‘The steps in Reduction Algorithm are as follows:
1, Combine all serial links by multiplying their path expressions
2. Combine all parallel links by adding their pathexpressions.
3. Remove all self-loops (from any node to itself) by replacing them with a
link of the form X*, where X is the path expression of the link in that loop.
STEPS 4 - 8 ARE IN THE ALGORIHTM'S LOOP:
4, Select any node for removal other than the initial or final node, Replace it
with a set of equivalent links whose path expressions correspond to all the
ways you can form a product of the set of inlinks with the set of outlinks
of that node.
Combine any remaining serial links by multiplying their pathexpressions.
Combine all parallel links by adding their pathexpressions.
Remove all self-loops as in step 3.
Does the graph consist of a single link between the entry node and the exit
node? If yes, then the path expression for that link is a path expression for
the original flowgraph; otherwise, return to step 4.
A flowgraph can have many equivalent path expressions between a given pair of
nodes; that is, there are many different ways to generate the set of all paths
between two nodes without affecting the content of that set.
‘The appearance of the path expression depends, in general, on the order in which
nodes are removed
waa
+ CROSS-TERM STEP (STEP 4):
The cross - term step is the fundamental step of the reduction algorithm.
It removes a node, thereby reducing the number of nodes by one.
Successive applications of this step eventually get you down to one entry and one
exit node. The following diagram shows the situation at an arbitrary node that has
been selected for removal:
From the above diagram, one can infer:
(at byc+d+e)=actad++ae+betbd tbe
4
