Theorem 6.4.4: each language equation system has a (unique) least solution, and the languages that occur as components of the least solution are context-free languages. Furthermore, each context-free language occurs in the least solution of its grammar viewed as an equation system.
Definition 6.4.4: language equation system s1 = (V1, _, e1) is subsumed by s2 = (V1_V2, _, e2), if every solution to s1 constitutes the components of at least one solution of s2 , and every solution to s2 restricted to V1 provides a solution to s1.
Lemma 6.4.1: each language equation system involving the * operation is subsumed by one without the * operation.
Previous slide | Next slide | Back to first slide | View graphic version |