Geben Sie den Regex-Baum für den regulären Ausdruck R := (b*|a*)(aaaaaa)(c*d*|b*) an.

Question

Geben Sie für den regulären Ausdruck R aus Teilaufgabe a) einen anderen regulären Ausdruck an, der auch hRi erzeugt und einen Regex-Baum benötigt, der niedriger ist als der Regex-Baum aus Teilaufgabe a). 

Answer 1

Der Regex-Baum für den regulären Ausdruck $$R:=(b^*|a^*)(aaaaaa)(c^*d^*|b^*)$$ sieht folgendermaßen aus:

(Die Ebenen des Regex-Baum durch graue Linien optisch voneinander getrennt)

Ein anderer (äquivalenter) regulärer Ausdruck \(R'\), der einen Regex-Baum mit niedrigerer Tiefe als \(R\) benötigt, ist:

\(R':=(b^*|a^*)((aaa)(aaa))(c^*d^*|b^*)\)