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
After substituting all ’s, the tree formed is as follows: [ [ ][ [ ]]][ [ ][ ]].