A Characterization of ET0L and EDT0L Languages

Peter R.J. Asveld

    Research output: Book/ReportReportOther research output

    60 Downloads (Pure)


    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)$.
    Original languageEnglish
    Place of PublicationEnschede
    PublisherUniversity of Twente
    Number of pages13
    Publication statusPublished - 1976

    Publication series

    NameMemorandum / Department of Applied Mathematics
    PublisherDepartment of Applied Mathematics, University of Twente
    ISSN (Print)0169-2690


    • HMI-SLT: Speech and Language Technology

    Cite this