# Section 1.3: Problem 6 Solution

Working problems is a crucial part of learning mathematics. No one can learn... merely by poring over the definitions, theorems, and examples that are worked out in the text. One must work part of it out for oneself. To provide that opportunity is the purpose of the exercises.

James R. Munkres

We have given an algorithm for analyzing a wff by constructing its tree from the top down. There are also ways of constructing the tree from the bottom up. This can be done by looking through the formula for innermost pairs of parentheses. Give a complete description of an algorithm of this sort.

Step 1. Denote the whole expression by
, and let
and the set of translations
be initially empty.

Step 2. If
is a sentence symbol or a symbol
then this is the root of the tree, stop(+).

Step 3. Search for the first right parenthesis, if there is no, stop(-). Search for the rightmost left parenthesis that is to the left of the found right parenthesis. If there is no, stop(-). Therefore,
where
has no parentheses in it. Increase
by 1, set
, form a vertex
, and substitute
for
in
. If
then form a leaf with
and set its parent to
, if
for some
, then set the vertex
created earlier as the only child of
, if
, where each of
and
is a sentence symbol or
for some
, then form new vertices corresponding to sentence symbols if necessary and set vertices corresponding to
and
as children of
, otherwise stop(-). Go to Step 2.

stop(+): the tree is formed, recursively substitute translations
’s into their parents

stop(-): the tree cannot be formed

Example:
.

children of | |||

, | |||

, | |||

, | |||

After substituting all
’s, the tree formed is as follows:
[
[
][
[
]]][
[
][
]].