# Re: Theory about DFA's and f?lex start states

## "Jonathan Barker" <ucapjab@ucl.ac.uk>

14 Nov 2000 13:09:32 -0500

*From comp.compilers*

| List of all articles for this month |

**From: ** | "Jonathan Barker" <ucapjab@ucl.ac.uk> |

**Newsgroups: ** | comp.compilers |

**Date: ** | 14 Nov 2000 13:09:32 -0500 |

**Organization: ** | [posted via Easynet] |

**References: ** | 00-11-073 00-11-080 00-11-083 |

**Keywords: ** | lex, parse |

**Posted-Date: ** | 14 Nov 2000 13:09:32 EST |

Paul

I won't give a highly rigorous development, but I think that

the following could be fleshed out to provide a proof that

a DPDFA is the same as the usual DPDA.

*> DPDFA is a system (M, K, f(m,k)) where:*

*>*

*> - M is a set of DFA's as above*

*>*

*> - K is a set of symbols called the "token" alphabet which is defined*

*> as the union of the output symbols over M (all the output*

*> symbols)*

*>*

*> - f(m,k) is a function mapping M X K to M (the mode transition*

*> function).*

You can easily combine all members of the set M into one big DFA

(call it D). For example, the set Q of states of D is the union of

the states of all X in M. It's easy to see that as long as

you name everything uniquely enough, you can define the transition

function.

*> Therefore, a DPDFA is a set of DFA's, not a single DFA. A lexer that*

*> uses a DPDFA may only be in one "mode" at a time (using one of the*

*> DFA's in M). When a token is recognized, the mode transition function*

*> is consulted to possibly move the lexer in a new "mode" (or "state").*

*> If these moves are done without a stack, you get flex. If the moves*

*> are done using a stack (and a special "pop" instruction in K), you get*

*> what I'm talking about.*

We must assume that your mode transition places the target DFA into its

start state. Hence we can think of f mapping states of D which

output "tokens" to the start state of the appropriate subset of D.

So now the transition function for D and the "mode transition"

function combined are effectively a goto function.

Now we've got a "goto" function and a big DFA. Seems to me that

this is a classical DPDA.

The key point here is that a set of DFAs is the same as one big

DFA. If I'm wrong, I expect that you'll find that a DPDFA is

equivalent to one of the other well-known models of computation.

It's just a matter of finding out which.

Hope this is of some help.

Jonathan

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.