We have thus shown that the path language of every recognizable DAG language is a regular string language.
the proof of this statement relies crucially on the fact that DAGs in [[M]] may have several roots: We considered the disconnected graph the latter may be connected and may thus, in fact, be an element of [[M ]], while containing the roots of both D 1 and D 2 .