- Introduction
- 1. 1.Introduction
- 2. 2.A Simple Syntax-Directed Translator
- 3. 3.Lexical Analysis
- 4. 4.Syntax Analysis
- 5. 5.Syntax-Directed Translation
- 6. 6.Intermediate-Code Generation
- 7. 7.Run-Time Environments
- 8. 8.Code Generation
- 9. 12.InterProcedural Analysis
- Published with GitBook
Exercises for Section 12.7
12.7.1
Using the encoding of symbols in Example 12.28, develop a BDD that represents the relation consisting of the tuples (b,b), (c,a), and (b,a). You may order the boolean variables in whatever way gives you the most succinct BDD.
Answer
12.7.2
As a function of n, how many nodes are there in the most succinct BDD that represents the exclusive-or function on n variables. That is, the functions is true if an odd number of the n variables are true and false if an even number are true.
Answer
For each variable, we put it on one layer. Their is only two possible arrangement left 0 or left 1. So for each variable, we need at most two nodes for it. And we need only one node for the first variable. So the answer is:
2n-1
For example, when n is 4:
12.7.3
Modify Algorithm 12.29 so it produces the intersection (logical AND) of two BDD's.
Answer
There are two places to modify:
a. BASIS: Zero variables. The BDD's must both be leaves, labeled either 0 or 1. The output is the leaf labeled 1 if both input are 1, or the leaf labeled 0 if either is 0.
b. INDEUCTION 2. ...The first of these BDD's represents the function that is true for all truth assignments that have y1 = 0 and that make both of the give BDD's true.