A computer-implemented method of finite state machine using constraint relaxation. A first expression having a plurality of variables is accessed. A second expression is accessed that describes a constraint with respect to a first variable of the plurality of variables. At least one of the variables from the second expression is eliminated to create a third expression with the constraint relaxed. The third expression is applied to the first expression to determine a finite state machine for the first expression.