22 Mar 2002 21:01:24 -0500

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) |

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.