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

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

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