21 Feb 2003 00:50:07 -0500

Related articles |
---|

DFA transition table reduction by alphabet reduction. criis@tyr.diku.dk (Christian Riis) (2003-02-21) |

Re: DFA transition table reduction by alphabet reduction. clint@0lsen.net (Clint Olsen) (2003-02-24) |

Re: DFA transition table reduction by alphabet reduction. criis@ivalde.diku.dk (Christian Riis) (2003-03-09) |

Re: DFA transition table reduction by alphabet reduction. gah@ugcs.caltech.edu (Glen Herrmannsfeldt) (2003-03-14) |

From: | Christian Riis <criis@tyr.diku.dk> |

Newsgroups: | comp.compilers |

Date: | 21 Feb 2003 00:50:07 -0500 |

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

Keywords: | lex, optimize, question |

Posted-Date: | 21 Feb 2003 00:50:07 EST |

Hi.

I'm writing a project about a certain scheme to reduce the size of DFA

transition tables. The idea is to make transtions on only a certain

number of the bits (half the bits for instance) in the letters in the

alfabet of a given DFA to an intermediate state and from there make

transitions on the rest of the bits. If one splits the transitions up

in two halves of equal size, the number of letters in the resulting

alfabet will of course have as many letters as the square root of the

number of letters in the original alfabet. What I'm hoping is, that

the number of states will increase less than the decrease of letters.

Does anyone in this forum know of any articles, books, whatever

written about this and if so, where can I find them?

Regards.

Christian Riis

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.