1. 状态集合
　　对有限状态系统而言，所谓状态一般就是由许多部件的值组成的（例如数字电路中的寄存器），并且每个部件用一个状态变量表示。令V = {v₀, …, v_n-1}为状态变量域，K_vi为变量v_i所有可能取值的集合，则通过指定V中所有变量的取值就可以确定一个具体的状态，所有可能的状态集合S_A为：
　　　　　　S_A ＝ K_v0 × K_v1 ×…× K_vn-1
对于状态s = {c₀, c₁,…, c_n-1}，则可以表示为下面的布尔函数：
　　如果是状态集合，则表示为各个状态所对应的布尔函数的"与"操作。
　　　　　　
　　例如，有3个状态变量v₁, v₂, v₃,（即3个触发器表示的状态），每个状态变量有2个取值：0和1，则S_A={0,1}′{0,1}′{0,1}={(000), (001), (010), (011), (100), (101), (110), (111)}, 共8个状态，设分别为A,B,C,D,E,F,G,H。通常有限状态机描述每两个状态之间的状态转换关系。而用BDD表示时，而要用布尔表达时是表示两个状态的各位状态变量之间的关系。

　　2. 状态转换关系
　　要将状态转换关系表示为布尔函数，首先需要引入状态对集合的概念。
　　状态对集合需要两个状态变量集合：V = {v₀, v₁,…, v_n-1} 代表当前状态变量的集合，V' = {v₀', v₁',…, v_n-1'} 代表次态变量的集合。V中的每个元素v在V' 中都存在一个次态变量v'。每个合法的状态转换就可以表示为关于V和V' 中的变量的一个布尔函数。同样，按照上一小节表示有限状态的方法，整个状态转换关系则表示为所有合法的状态转换的"或"操作。我们将布尔函数表示的状态转换关系表示为N(V, V')。
　　更进一步，我们可以通过分别定义每个状态变量的转换函数来描述整个有限状态系统的状态转换。令V = {v₀, v₁,…, v_n-1}, V' = {v₀', v₁',…, v_n-1'}。则对于每个状态变量v_i'，存在一个函数fi，使得 v_i' = f_i(V)。则v_i的转换关系N_i的BDD可以表示为：
　　　　　　N_i( V,V')：= (v_i'= f_i(V))
对于同步电路而言，由于所有的状态变量同时发生变化，因此，总体的状态转换关系N(V, V') 即为所有状态变量的转换关系的"合取"操作：
　　　　　　N( V, V') = N₀(V, V') ∧ N₁(V, V') ∧ … ∧ N_n-1(V, V')
　　在有限自动机中，次态是现态的函数，用状态变量的关系表示，次态每一位v'i与现态各位v0, v1,…, vn-1的函数。即vi' = fi (v0, v1,…, vn-1)，简记为：vi' = fi (V)。当然，对次态的n个位都有这样的一个函数，一共有n个函数，他们是合取的关系，也就是与的关系。