18 Mar 2005 00:44:52 -0500

Related articles |
---|

Finite State Automaon Question vborkyREMOVE_THIS@yahoo.com (Vinayak R. Borkar) (2005-03-15) |

Re: Finite State Automaon Question torbenm@diku.dk (2005-03-18) |

Re: Finite State Automaon Question vborky@yahoo.com (Vinayak R. Borkar) (2005-03-20) |

Re: Finite State Automaon Question torbenm@diku.dk (2005-03-24) |

Re: Finite State Automaon Question peter.ludemann@gmail.com (2005-03-24) |

Re: Finite State Automaon Question nathan.moore@sdc.cox.net (Nathan Moore) (2005-03-25) |

Re: Finite State Automaon Question vborky@yahoo.com (Vinayak R. Borkar) (2005-03-31) |

Re: Finite State Automaon Question torbenm@diku.dk (2005-04-02) |

From: | torbenm@diku.dk (=?iso-8859-1?q?Torben_=C6gidius_Mogensen?=) |

Newsgroups: | comp.compilers |

Date: | 18 Mar 2005 00:44:52 -0500 |

Organization: | Department of Computer Science, University of Copenhagen |

References: | 05-03-058 |

Keywords: | lex, theory |

"Vinayak R. Borkar" <vborkyREMOVE_THIS@yahoo.com> writes:

*> Hi,*

*>*

*> At work we were faced with the following problem.*

*>*

*> Consider two regular languages L1, and L2. It is known that*

*> L2 = L1, L3 where L3 is yet another regular language.*

*>*

*> Given L1 and L2, what is the algorithm to find L3?*

*>*

*> I realize that L3 may not be unique for any given L1 and L2.*

*> All I need is any one L3 that satisfies the above relation.*

*>*

*> What would be a good place to look for this kind of analysis?*

*>*

*> I have a method in mind to figure a possible L3. It would be*

*> great if someone could show if it is right or wrong, and why.*

[Method deleted]

I can't offhand determine if your method is O.K., but here is an

alternative:

Given DFA's D1 and D2 for L1 and L2, make a DFA D3 where each state in

D3 is a pair of states from D1 and D2 and there is a transition from

(s1,s2) to (t1,t2) on symbol c if there are transitions from s1 to t1

and s2 to t2 in D1 and D2, respectively. Start with the pair of start

states from D1 and D2 and find all that are reachable from this.

Since any string in L1 is a prefix of a string in L2, all states from

D1 will be represented in at least one pair of states in D3.

Now look at the set S of states s2 where there exist a pair (s1,s2) in

D3 such that s1 is an accepting state of D1. Make a new

(nondeterministic) automata N that has the states of D2 but a new

initial state s0 that has epsilon transitions to all the states in S.

The final states are unchanged.

Let us imagine a string w in L3. Then there exists a string v in L1

such that vw is in L2. This means that we after reading v in D3 will

reach a state that is a pair of a final state s1 from D1 and a state

s2 from D2. Starting from s2, we can in D2 reach a final state after

reading w (as vw is accepted by D2), so w will also be accepted by N.

Conversely, assume a string w accepted by N. The first transition in

N is an epsilon transition to a state s2 from D2. But since there is

a pair of states (s1,s2) in D3, where s1 is accepting in D1, there

exist a string v in L1 such that in D2, v leads to s2. Hence, vw will

be accepted by D2, so vw is in L2.

Torben

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.