|Subset of a language algorithm? email@example.com (Paul J. Lucas) (2002-03-21)|
|Re: Subset of a language algorithm? firstname.lastname@example.org (2002-03-22)|
|From:||email@example.com (David Wagner)|
|Date:||22 Mar 2002 21:01:24 -0500|
|Organization:||University of California, Berkeley|
|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
>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.
Return to the
Search the comp.compilers archives again.