<jupyter_start><jupyter_text>** IMPORTANT NOTE: RESTART AND RUN ALL CELLS SO THAT THE STATES GET NUMBEREDCORRECTLY AS PER THE EMBEDDED DESCRIPTIONS IN THIS NOTEBOOK **<jupyter_code># Reset the state numbering counter
ResetStNum()<jupyter_output><empty_output><jupyter_text>BDDs: Efficient Data Stuctures for Boolean Function Representation  Boolean functions occur widely in computer science. In order to represent and manipulate large Boolean functions, one must choose good data structures. A data structure called BDDs often works well. In fact, Prof. <NAME> [has said](https://en.wikipedia.org/wiki/Binary_decision_diagram)  in his lecture _Fun With Binary Decision Diagrams_  that BDDs are"one of the only really fundamental data structures  that came out in the last twenty-five years."  We are studying BDDs in our book because BDDs are nothing but a small variant of  minimal DFAs for a simple language that one can obtain from a given Boolean function. Given that we have studied minimal DFAs extensively, it looks quite opportune to point out yet another amazing connection in computer science -- specifically, the study of Boolean functions being another application of minimal DFA.  In this narrative, we will cover all the required basics one by one; we assume very little by the way of prerequisites.  Boolean functions, and viewing their on-sets as formal languages A Boolean function f(x1,x0) admits a truth-table of four entries with thetruth-table output (called "personality") defining the function for thestandard order of enumeration of x0 and x1. For AND, taking the inputs x1,x0 through 00, 01, 10 and 11, the outputs of AND are 0001 (the string0001 is its personality). The personality has $2^2$ bits (for a $2$-inputBoolean function). There are $2^{2^2} = 16$ personalities for a $2$-inputBoolean function. Each personality defines a Boolean function; thus, thereare $16$ possible Boolean functions.Here are personalities of some common functions: ``` Inputs  Personalities----------------------| x1 x0 | OR XOR NOR |----------------------| 0  0  | 0  0   1   || 0  1  | 1  1   0   || 1  0  | 1  1   0   || 1  1  | 1  0   0   |----------------------```In general, an $N$-input truth-table has $2^N$ truth-table rows and a personality of length $2^N$, thus admitting $2^{2^N}$Boolean functions of $N$ inputs.It is impractical (and insane) to be building truth-tables for Boolean functions withmany inputs. Even a $64$-input Boolean function will have a truth-table of $2^{64}$ rows.Suppose we want to even print one such truth-table. At 80 rows printed per sheet of paper andfive grams of weight per sheet, we will need 46-billion tons of paper to print. Even a newborn human baby would be dead of ripe old age by the time this many pages are printed.Yet, there is a method by which _many_ 64-input Boolean functions can be exactlyrepresented using alternative representations than truth-tables. (To emphasize this a bit,not all functions can be so represented, but it works for many Boolean functions occurring in practice.)One such representation is called a Binary Decision Diagram.Binary Decision Diagrams (BDD) are graph structures that summarize a Boolean function'son-sets (sets of inputs for which the function is true). The on-set of the AND functionis {11} while that for the OR function is {01, 10, 11}.One can read on-sets as a formal language. The language of an OR-gate is thus {01, 10, 11}(its on-set) and the language of (the on-set of) an AND-gate is {11}.  Minimal DFA for the on-set of an XOR and ORIn order to drive the point home with respect to how minimal DFA can be made to encodethe on-set of functions, let us build a minimal DFA for the language of XOR's on-set and also OR's on-set.<jupyter_code>L_XOR = "(01+10)"
dotObj_dfa(min_dfa(nfa2dfa(re2nfa(L_XOR))), STATENAME_MAXSIZE=4)
doXOR = dotObj_dfa(min_dfa(nfa2dfa(re2nfa(L_XOR))), STATENAME_MAXSIZE=4)
doXOR.render('/Users/ganesh/repos/atmm/book/CH17/XORdfaNoBH.dot')<jupyter_output><empty_output><jupyter_text>It is easy to see that both 01 and 10 lead to the final state, namely St8, whereas 00 and 11 go to BH. Also excessively long inputs (of length more than two) also go to BH.<jupyter_code>L_OR = "(01+10+11)"
dotObj_dfa(min_dfa(nfa2dfa(re2nfa(L_OR))), STATENAME_MAXSIZE=4)
doOR = dotObj_dfa(min_dfa(nfa2dfa(re2nfa(L_OR))), STATENAME_MAXSIZE=4)
doOR.render('/Users/ganesh/repos/atmm/book/CH17/ORdfaNoBH.dot')<jupyter_output><empty_output><jupyter_text>One can build BDDs corresponding to these functions as will be describe in the book. Also see the section at the end on building BDDs.It is easy to compare the BDDs to these minimal DFA and note the following:* The minimal DFA keep edges marked 0/1 . The BDD eliminates such "redundant decoding" edges, short-circuiting the graph at those edges* The minimal DFA shows what happens when strings with excessive lengths are fed. The BDD stops with a ``0'' node or a ``1'' node at the leaf, and does not carry on to show what happens when an excessively long string is fed.* The BDD does show the BH state as the ``0'' node.So far, the advantage of minimal DFA (or BDD) over truth-tables hasn't been quite apparent. We now proceed to demonstrate that for larger functions, with the right decoding order of the variables, BDDs (and minimal DFA) can indeed be far more compact (whereas truth-tables are guaranteed exponential)  Building minimal DFA for the language of on-sets Suppose there is a 6-input Boolean function modeling a magnitude comparator that compares the binary value coming in through input ports x2,x1,x0 against the binaryvalue coming through ports y2,y1,y0.The function is "<" where "A < B" means the usual "less than" comparison.More specifically, we write "x2,x1,x0 < y2,y1,y0" and we interpret the word x2,x1,x0using the standard positional binary notation (likewise also for y2,y1,y0).Here are some examples:* 000 < 001  because 0 is < 1  (and 0 is encoded in binary as 000 and 1 as 001)* 010 < 110  because 2 is < 6  (and 2 is encoded as 010 while 6 is encoded as 110)* 110 < 111  because 6 < 7```Here is a circuit schematic of such a comparator:      --------      |      |x2 -->|      |x1 -->|      |x0 -->|      |      |    Outputy2 -->|      |y1 -->|      |y0 -->|      |      |      |      --------```Let us now define a language of strings of length 6 representing the values of x2,x1,x0,y2,y1,y0 written adjacently, such that for those x,y values, the functionoutputs a 1. Call this language L.For instance, L contains 010101 because 010 is < 101 (i.e. 2 < 5)The reader may verify that this is the full L language written out as a regular expression.Of the $2^6 = 64$ strings, we have 28 strings in L's language. The regular expression for L is called R, and is defined below:```R =     "(000001+000011+000111+001011+001111+\          010011+010111+011111+100101+100111+\          101111+110111+000010+000101+000110+\          001010+001101+001110+010101+010110+\          011101+011110+100110+101110+000100+\          001100+010100+011100)"```Let us build a minimal DFA for R.<jupyter_code>R =     "(000001+000011+000111+001011+001111+\
          010011+010111+011111+100101+100111+\
          101111+110111+000010+000101+000110+\
          001010+001101+001110+010101+010110+\
          011101+011110+100110+101110+000100+\
          001100+010100+011100)"
N      = re2nfa(R)
Dbloat = nfa2dfa(N)
D      = min_dfa(Dbloat)
doBadLTNoBH = dotObj_dfa(D, FuseEdges=True)
doBadLTNoBH
doBadLTNoBH.render('/Users/ganesh/repos/atmm/book/CH17/doBadLTNoBH.dot')<jupyter_output><empty_output><jupyter_text>This machine appears to be rather large -- in fact exponential in the x2,x1,x0 bits (those are the first three bits to arrive at this machine, and the machine grows exponentially with respect to these inputs). It then collapses soon as soon as the y bits come in.Size aside, this DFA acts as a representation of the "<" function. Take the starting state: all paths from it leading to the final state are in the on-set of this function; any path of length six that goes to the BH state is in the off-set of this function. Strings of length greater than six can be entertained, but they have no meaning with respect to our problem that involves only six variables. Let us take an example. String 001100 is accepted. Here is the accepting path:* St1 --0--> St18 --0--> St22 --1--> St32 --1--> St27 --0--> St9 --0--> St35 The rejecting paths include strings of length six that are not in the language being modeled, or strings of higher lengths than six. These strings cause the execution to enter the "black hole" state (that is not shown in our diagrams). Also notice that the _nodes_ in this minimal automaton graph represent Boolean functions. Thus, state St1 is a function of all the six input bits. States St18 and St8 are functions of the five bits x1,x0,y2,y1,y0. In fact, the further we go away from the initial state, the lesser the remaining bits are in deciding the "fate of the function". Take state St18 which is one step away from the initial state. All paths leading to the final state represent the on-set of a Boolean function of inputs x1,x0,y2,y1,y0. Paths leading to state BH (not shown) are in the off-set (not shown) But suppose another astute person jumps in and tells us that it will be a small minimal DFA if we were to have considered strings x2,y2,x1,y1,x0,y0 to be in the language. That is, we mix the bits (and call the language Lmix, and the regular expression Rmix).We have the following Rmix.<jupyter_code>Rmix =  "(000001+000111+001101+011111+110001+\
          110111+111101+000101+000110+010111+\
          011011+011101+011110+110101+110110+\
          000100+010011+010101+010110+011001+\
          011010+011100+110100+010001+010010+\
          010100+011000+010000)"<jupyter_output><empty_output><jupyter_text>We still have 28 entries, but the entries now represent x2,y2,x1,y1,x0,y0. For instance,take the fifth member of Rmix which is 110001. This means 100 < 101 which means 4 < 5, which is true. Let us now build a minimum DFA for Rmix.<jupyter_code>Dmix = min_dfa(nfa2dfa(re2nfa(Rmix)))
doGoodLTNoBH = dotObj_dfa(Dmix, FuseEdges=True)
doGoodLTNoBH
doGoodLTNoBH.render('/Users/ganesh/repos/atmm/book/CH17/doGoodLTNoBH.dot')<jupyter_output><empty_output><jupyter_text>We see that this minimal DFA is much smaller. The reason is that as soon as an x2 comes, a y2 bit is fed. In a positional encoding of binary numbers, this allows a DFA to immediately decide whether X < Y for X = x2x1x0 and Y = y2y1y0. The DFA that sees x2,x1,x0,y2,y1,y0 on the other hand cannot take a decision until bit y2 comes along. This means that this DFA has to build a full tree after seeing merely x2,x1,x0 and this would already be exponential in size.  This machine appears to be linearly sized w.r.t. the number of inputs. This DFA also acts as a representation of the "<" function.  State St1 is a function of all the six input bits. States St2 and St3 are functions of the five bits y2,x1,y1,x0,y0. In fact, the further we go away from the initial state, the lesser the remaining bits are in deciding the "fate of the function". But the bits come in an interleaved manner. Take St2 as representing a Boolean function: paths from it to the final state represent the on-set of a Boolean function of inputs y2,x1,y1,x0,y0 and paths leading to BH are in the off-set.  Boolean subfunctions in the DFAEach state of the minimal DFA obtained in this manner represents a Boolean function.  Building BDDs from minimal DFA for on-set languagesA BDD is obtained from a minimal DFA by following some "cleanup" steps:* When a 0,1 jump is made from one state to the other, short-circuit the jump   - This means that whether a 0 or a 1 comes, we go to the same state. That is     a redundant binary decoding situation    * When we see two distinct nodes represent the same Boolean function, merge them   - This merging step is already being done during state minimization   Let us obtain BDDs using our BDD tool and then compare it with our minimal DFA to get an idea of what these optmizations do.<jupyter_code>import webbrowser

# This is the URL for our BDD tool that can be opened on a new tab
url = 'http://formal.cs.utah.edu:8080/pbl/BDD.php'
webbrowser.open(url)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.07674778220883861, 'fraction_numerical': 0.06852771221616343, 'mean_word_length': 4.086092715231788, 'pattern_counts': {'":': 0, '<': 46, '<?xml version=': 0, '>': 42, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '7', 'dir': 'jupyter-structured-clean-dedup', 'id': '127511', 'license': 'Unlicense', 'n_tokens_mistral': 4140, 'n_tokens_neox': 3550, 'n_words': 1742, 'path': 'First_Jove_Tutorial/CH17/CH17.ipynb', 'repo_name': 'Thanhson89/JA', 'size': '12293'}