A Characterization of ET0L and EDT0L Languages
P.R.J. Asveld · University of Twente Research Information · 1976
There exists a PT0L language $L_0$ such that the following holds. A language $L$ is an ET0L language if and only if there exists a mapping $T$ induced by an a-NGSM (nondeterministic generalized sequential machine with accepting states) such that $L = T(L_0)$. There exists an infinite collection of EPDT0L languages $D_{mn}\\subseteq\\Sigma_{mn}^\\star$ ($n\\geq m\\geq 1$) such that the family EDT0L is characterized in the following way. A language $L$ is an EDT0L language if and only if there exists $n\\geq m\\geq 1$, a homomorphism $h$ and a regular language $R \\subseteq \\Sigma_{mn}^\\star$ such that $L = h(D_{mn} \\cap R)$.