On Equivalence and Containment Problems for Formal Languages
Harry B. Hunt, Daniel J. Rosenkrantz · Journal of the ACM · 1977
Sufficient but general conditions on a family of formal languages ~ and a language L~ m ~ are given such that (l) "'= L0" is as hard as "= {0, 1}*" for,~', (2) "_~ Lo" is as hard as "= {0, 1}*" for if', and (3) "= L0" and "C_ Lo" are as hard as "= ~" lor ~: For many interesting families such as the regular sets and contextfree languages, a sufficient condmon for (1) is that Lo has an unbounded regular subset; a sufficient condinon for (2) is that Lo has an unbounded context-free subset, and a sufficient condition for (3) is that L0 has no unbounded regular subsets Numerous applications of these results to specific families of languages are hsted Many context-free languages are shown to contain unbounded regular subsets KEY WORDS AND PHRASES equivalence, containment, language, grammar, context-free CR CATEGORIES 5 22, 5 23, 5 25 IntroducttonFor a family of languages and a fixed language L0 m the family, a deoston problem of mterest is: Given a description of a language m the family, does that language equal L0 Two other related problems are: Does the language contain Lo, and is the language contained in Lo We abbrevtate the above three problems as "= L0," "_~ Lo," and "C L0," respectively.In this paper we show that for many interesting famdies of languages and fixed languages L0 in ~,~, "= L0'" ts as hard as "= {0, 1}*" or "= {0, 1} +'' for ~, whenever Lo has an unbounded regular subset.Slmdarly "~ L0" is as hard as "= {0, 1}*" or "= {0, 1}+, '' whenever L0 has an unbounded context-free subset.Finally "= Lo" and "_CL0" are as hard as "= ~" for if, whenever Lo has no unbounded regular subsets This ts true for famdles with deodable "= {0, 1}*" and "= Q" problems as well as families for which these problems are undecldable.To mvestlgate the complexity of these predicates for general classes of languages, we mtroduce the concept of an effective famdy of languages over {0, 1}.In Sections 2 and 3 we show that for all effectwe famdies of languages that are "efficiently" closed under several simple language operations these results hold, In Section 4 examples are gtven where these general results apply In