Re: Subset of a language algorithm?

daw@mozart.cs.berkeley.edu (David Wagner)
22 Mar 2002 21:01:24 -0500

          From comp.compilers
Related articles
Subset of a language algorithm? pjl.removethis@removethistoo.mac.com (Paul J. Lucas) (2002-03-21)
Re: Subset of a language algorithm? daw@mozart.cs.berkeley.edu (2002-03-22)
| List of all articles for this month |
From: daw@mozart.cs.berkeley.edu (David Wagner)
Newsgroups: comp.compilers
Date: 22 Mar 2002 21:01:24 -0500
Organization: University of California, Berkeley
References: 02-03-139
Keywords: theory
Posted-Date: 22 Mar 2002 21:01:24 EST

Paul J. Lucas wrote:
>In "Intro. to Automata Threory, Languages, and Computation," an
>algorithm is given for testing whether two languages are
>equivalent.
>
>Is there an algorithm for testing whether one language accepts a
>subset of another? If so, can somebody point me at it? Thanks.


I take it you're referring to regular languages (otherwise, your first
sentence isn't true in general).


Say L, L' are two regular languages. Note that we have
    L subset L' if and only if L intersect complement(L') = emptyset.
Moreover, given L', we can effectively compute the regular
language L'' = complement(L') = \Sigma^* \ L', and given L,L''
we can effectively compute L''' = L intersect L'', and given
L''' we can effectively test whether this language is empty.
(The last three properties should be explained in any good language
theory textbook.) This will then answer your question.

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.