Normal forms for bicolored-digraph-grammar systems
Gheorghe Pacaronun · International Journal of Computer Mathematics · 1979
We prove that for any bicolored-digraph-grammar system without choice there is an equivalent such system in canonical form. This provides an alternative solution (cf. [3]) to Problem 1 raised by D. Wood in [2]; the choice does not modify the generative capacity of these systems. Then it is shown that for any bicolored-digraph-grammar system (with or without choice) there is an equivalent binary system. Finally we shall prove that the generative capacity of these systems is not modified by considering initial vertices in the graph. This is true also for final vertices