31 Mar 2002 23:30:06 -0500

Related articles |
---|

DFA complement/intersection problem pjl@mac.com (Paul J. Lucas) (2002-03-31) |

Re: DFA complement/intersection problem rcbilson@plg2.math.uwaterloo.ca (2002-04-06) |

Re: DFA complement/intersection problem mickunas@cs.uiuc.edu (Dennis Mickunas) (2002-04-06) |

Re: DFA complement/intersection problem heinrich@idirect.com (Kenn Heinrich) (2002-04-06) |

DFA complement/intersection problem cfc@world.std.com (Chris F Clark) (2002-04-06) |

From: | "Paul J. Lucas" <pjl@mac.com> |

Newsgroups: | comp.compilers |

Date: | 31 Mar 2002 23:30:06 -0500 |

Organization: | Prodigy Internet http://www.prodigy.com |

Keywords: | lex, DFA, theory |

Posted-Date: | 31 Mar 2002 23:30:06 EST |

If I have two languages:

L = a*

M = (a|b)*

it's obvious that L <= M (L is a subset of M) because all

sequences of A* are also sequences of (a|b)*. However, when I

write code for this, I get L <= M and M <= L which is wrong.

From:

L <= M === intersect(L,~M) = 0

I first have two minimal DFA for both languages:

L: (s0) --{a}-> (s0)

M: (t0) --{a|b}-> (t0)

That is: each DFA has a single state that is accepting. For L,

there is a single transition on 'a' back to s0; for M, there

are two transitions: one each for 'a' and 'b' back to t0.

If I understand Hopcroft, et al, correctly, to compute ~M, the

complement of M, you simply flip all the accepting and non-

accepting states. For M, since there is only one state, it

becomes non-accepting.

Then, to compute the intersection, you do a cross product of

all the states in L and M and relabel each pair of states (p,q)

in the intersected langauge N. (You also do stuff with the

transitions, but that's not relevant here.) Furthermore, a

state in N is accepting iff (p,q) is accepting.

Now, since ~M has no accepting states, N can't either; therefore

N is empty and this shows that L <= M.

However, if you do this for M <= L, you get the same result

because ~L has no accepting states so N' = intersect(M,~L)

doesn't either; therefore N' is empty and M <= L. But this

isn't right!

What am I missing? Where is the mistake.

- Paul

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.