Cornell University
Library
Cornell UniversityLibrary

eCommons

Help
Log In(current)
  1. Home
  2. Cornell Computing and Information Science
  3. Computer Science
  4. Computer Science Technical Reports
  5. On the Equivalence and Containment Problems for Context-Free Languages

On the Equivalence and Containment Problems for Context-Free Languages

File(s)
68-19.pdf (451.79 KB)
68-19.ps (198.81 KB)
Permanent Link(s)
https://hdl.handle.net/1813/5872
Collections
Computer Science Technical Reports
Author
Hopcroft, John E.
Abstract

Let $G$ and $G_{0}$ be context-free grammars. Necessary and sufficient conditions on $G_{0}$ are obtained for the decidability of $L(G_{0}) \subseteq L(G)$. It is also shown that it is undecidable for which $G_{0},L(G) \subseteq L($G_{0})$ is decidable. Furthermore, given that $L(G) \subseteq L($G_{0})$ is decidable for a fixed $G_{0}$, there is no effective procedure to determine the algorithm which decides $L(G) \subseteq L($G_{0})$. If $L(G_{0})$ is a regular set, $L(G)=L(G_{0})$ is decidable if and only if $L(G_{0})$ is bounded. However, there exist non-regular, unbounded $L(G_{0})$ for which $L(G) = L(G_{0})$ is decidable.

Date Issued
1968-06
Publisher
Cornell University
Keywords
computer science
•
technical report
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR68-19
Type
technical report

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

copyright © 2002-2026 Cornell University Library | Privacy | Web Accessibility Assistance