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

pcj1@my-deja.com wrote:


> Chris, I don't think you read my post thoroughly enough. I'm not
> talking about deterministic pushdown automata (DPDA) though the name
> "deterministic pushdown finite automata" (DPDFA) is clearly very
> similar (by intent).
>
> A DPDA is not a DPDFA. Let me explain (excuse the formality, it's for
> my own good)
>
> ==================================================
>
> [...]
>
> What I'm talking about
>
> 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).
>
> 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.
>
> So while both DPDA's and DPDFA's use dfa's and stacks, they are quite
> different. The languages that may be derived from either are
> different, therefore they are not the same (though I have not proved
> that).
>
> Since I'm obviously in the belief that "DPDFA" is a unique animal, I'm
> looking for more information about it such that I don't have to spin
> and or re-invent wheels (general laziness).
> [Interesting question. It feels to me like it's equivalent to a DPDA
> but my comp theory isn't good enough to prove it either way. -John]


I don't really feel like putting up a formal proof (not at this time
of night, anyway), but I think the basic idea to prove equivalence
would be to identify pairs of DPDFA states and active DFA (M x Q,
assuming for simplicity that all DFAs have the same set of states)
with DPDA states (i.e., construct a DPDA such that the transitions fit
this identification).


This is under the assumption that the choice of next DFA depends
only on the current DFA, the token and the state of the stack (i.e.,
something like f: M x K x A -> M x A where A is the (infinite) set
of stack states, and f "respects stack semantics").


If, however, the push/pop operations can be part of arbitrary C
coded rules (to use lex terminology), as in your original request,
this doesn't hold. But then, already lex with C rules is a Turing
machine, and so is anything more powerful including arbitrary C
rules...


Technical side note: You can do what you want perfectly well in lex
(at least GNU flex -- don't know about the original lex). The
argument of BEGIN is not required to be a constant, so you can use
your favourite stack implementation and call BEGIN (top of stack)
after each push and pop.


Frank


--
Frank Heckenbach, frank@[NOSPAM.REMOVE.THIS]g-n-u.de, http://fjf.gnu.de/
PGP and GPG keys: http://fjf.gnu.de/plan
Pascal code, BP CRT bugfix: http://fjf.gnu.de/programs.html
Free GNU Pascal Compiler: http://home.pages.de/~GNU-Pascal/

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