Definition 6.4.2: a language equation system s = (V, _, e) is a triple where V is a finite collection of unknowns (or variables), say V = {X1, X2, … , Xn}, _ is an alphabet disjoint from V, and e is a collection of equations X1 = e1, X2 = e2, … , Xn = en, where each ei is a regular expression over V ___.
A solution for this equation system is an n-tuple of languages of _*, _ = < _1, _2, … , _n>, such that _i = ei(_) is a valid set equality for each i, 1ŠiŠn, where ei(_) is the language resulting from replacing each instance of variable Xi in ei (1ŠiŠn) by the language _i and performing the language operations indicated by ei. s is inconsistent if it has no solutions; otherwise it is consistent.
| Previous slide | Next slide | Back to first slide | View graphic version |