4 Aug 2002 11:42:53 -0400

Related articles |
---|

determining which bin contains which string partha@berkeley.innomedia.com (Partha Saha) (2002-08-04) |

Re: determining which bin contains which string vbdis@aol.com (VBDis) (2002-08-10) |

Re: determining which bin contains which string ralph@inputplus.co.uk (Ralph Corderoy) (2002-08-14) |

Re: determining which bin contains which string jakacki@hotmail.com (Grzegorz Jakacki) (2002-08-23) |

From: | "Partha Saha" <partha@berkeley.innomedia.com> |

Newsgroups: | comp.compilers |

Date: | 4 Aug 2002 11:42:53 -0400 |

Organization: | Compilers Central |

Keywords: | lex, question |

Posted-Date: | 04 Aug 2002 11:42:53 EDT |

I was seeking a solution to the following problem:

I have strings of length 12, the alphabets are 0-9,a,b,c,d,e,f (i.e.,

they are "hexadecimal" strings). Clearly the number of strings

possible is huge = 16^12

Let's say we have a finite number of them (N where is N is large, say

100000, but N << 16^12). These have been binned by some arbitrary

logic into n (where n is say 5, n << N) bins. The bins are numbered

from 1 to n.

Instead of keeping a table of N rows where each row has a mapping of

string to bin number, I am wondering if I could design a finite state

machine which would take a string, go through each string element, and

end up in a final state that corresponds to a bin number (of course if

the string is not one of the N strings, it should go into a

non-accepting state).

I would also like to dynamically alter the FSM as N->N+1, i.e., as new

strings get added to our set. and put into a certain bin (we cannot

predict which bin that would be).

I would also like to dynamically alter the FSM as n->n+1, i.e., as new

bins are added (but the contents of the previous bins are left

unaltered).

My training being in Physics, I can probably "hack" up a solution; I

was wondering if someone knew of a formal way of going about it.

Somehow a proof is also needed that the storage requirements of the

FSM will be better than the actual table itself.

Thanks much!

Partha Saha

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.