Let $T_1,T_2 \subseteq T_\Sigma$ be regular tree languages, f a symbol with arity 2.

To proof: $\{f(t_1,t_2) \mid t_1 \in T_1, t_2 \in T_2\} \subseteq T_{\Sigma \cup \{f\} }$ is regular.

So it's basicaly a tree with f as root and t1 and t2 as left and right children.

My Idea:

I tried to proof regularity by giving a deterministic Tree automaton and I thought to evalute all leafs on the left side with the transition function of t1 and the right side with transition function of t2, and would check if both or one of them end up in an accepting state. The problem is to decide when i should take function t1 or t2.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.