The Inclusion Problem for Some Subclasses of Context-Free Languages

P.R.J. Asveld, Antinus Nijholt

    Research output: Book/ReportReportAcademic

    86 Downloads (Pure)


    By a reduction to Post's Correspondence Problem we provide a direct proof of the known fact that the inclusion problem for unambiguous context-free grammars is undecidable. The argument or some straightforward modification also applies to some other subclasses of context-free languages such as linear languages, sequential languages, and DSC-languages (i.e., languages generated by context-free grammars with disjunct syntactic categories). We also consider instances of the problem ``Is $L(D_1 )\subseteq L(D_2 )^$ ?'' where $D_1$ and $D_2$ are taken from possibly different descriptor families of subclasses of context-free languages.
    Original languageUndefined
    PublisherCentre for Telematics and Information Technology (CTIT)
    Number of pages7
    Publication statusPublished - 1997

    Publication series

    NameCTIT Technical Report Series
    ISSN (Print)1381-3625


    • EWI-10932
    • METIS-118509
    • IR-64305
    • HMI-SLT: Speech and Language Technology

    Cite this