Re: DFA transition table reduction by alphabet reduction.

  Christian Riis wrote:
> 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.


I don't see why you absolutely need to use transition tables. If you
use the directly executable method of this using explicit character
range tests, the transitions should be quite compact. Re2c uses this
technique. If there are a lot of transitions out of a particular
state it splits the ranges using a binary search technique to minimize
the number of tests.


I can't get to the re2c homepage now, but I believe it's at:


http://www.tildeslash.org/re2c


-Clint

Return to the comp.compilers page.
Search the comp.compilers archives again.