On the equivalence and containment problems for context-free languages | Zendy

John E. Hopcroft | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

On the equivalence and containment problems for context-free languages

Author(s) -

John E. Hopcroft

Publication year - 1969

Publication title -

mathematical systems theory

Language(s) - English

Resource type - Journals

ISSN - 0025-5661

DOI - 10.1007/bf01746517

Subject(s) - decidability , undecidable problem , equivalence (formal languages) , mathematics , context (archaeology) , bounded function , combinatorics , context free language , discrete mathematics , set (abstract data type) , context free grammar , rule based machine translation , computer science , programming language , natural language processing , paleontology , mathematical analysis , biology

LetG andG0 be context-free grammars. Necessary and sufficient conditions onG0 are obtained for the decidability ofL(G0) $\subseteq$ L((G) It is also shown that it is undecidable for whichG0,L(G) $\subseteq$ is decidable. Furthermore, given thatL(G) $\subseteq$ is decidable for a fixedG0, there is no effective procedure to determine the algorithm which decidesL(G) $\subseteq$ IfL(G0) is a regular set,L(G) = L(G0) is decidable if and only ifL(G0) is bounded. However, there exist non-regular, unboundedL(G0) for whichL(G) = L(G0) is decidable.