I need to generate a transition state table. To do that, I find the combinations of rules that can be applied to a given rule. Before I can do that, note that nested rules are replaced by 'accented' values:
(tile: at (a (t)) r) becomes
(tile: at2 (t) t')
(tile: at (a t') r)
Hence, according to this, the (t) node can generate both r and t', and this is indistinguishable form the perspective of the (t) node. For this reason, rules t1 and at2 should be combined (the tiler can choose the correct one on the basis of the parent node).
The question is mostly to determine what rules can be combined in what ways. From our inspection, a1 can be combined with at1, a1 can be combined with as1, but as1 can never be combined with at1. (The child node cannot both be (t) and (s). Similarily, a1 can occur separately from at1 or as1, but not the other way arround, because if we can pick at1 we can always pick a1 too because (a (t)) may reduce to (a r).
The valid rulesets are:
(t) -> {t1, at2}
(s) -> {s1, as2}
(a r) -> {a1}
(a (t)) -> {a1, at1}
(a (s)) -> {a1, as1}
I use a topological sort to determine 'dependencies'. Nodes starting with (t) and (s) do not depend on anything; their rulesets can be readiliy generated. In constrast, nodes starting with a depend on the rulesets generated by (t) and (s). They also depend on all rulesets generating r, but since that includes the 'a' rules themselves, this generates a cycle, which has to be broken for the rulesets to be generated at all.
The execution of the algorithm now look like this: Starting with (t), generate t1 -> r and at2 -> t', yielding ruleset {t1, at2} (terminal set {r, t'}) Then with (s), generate s1 -> r and as2 -> s', yielding ruleset {s1, as2} (terminal set {r, s'}) Because (a) is cyclically blocked, unblock it by removing the dependency on r, generate (on the basis of these rules):
(a {r,t'}) -> r yields {a1, at1}
(a {r,s'}) -> r yields {a1, as1}
However, no combination yields {a1} alone, while this is a possible ruleset that can be generated.