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

> [Its not Arpil 1st is it?]
>
> Yes there's lots of research on these things, though they're usually
> referred to as D-PDAs (Deterministic Push Down Automata). They're the
> technique used by yacc and similar tools to parse CFGs.
>
> The standard intro textbook on this topic is the Hopcroft & Ullman
> automata book (which I don't have right in front of me, or I'd give
> you the actual title and ISBN).
>
> Chris Dodd
> chrisd@reservoir.com
> [Oh, right, it's true, a state machine plus a state stack basically
> gives you yacc. -John]


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)


==================================================


A pushdown automaton M is a system (Q, T, N, f(q,s), q0, n0, F) where:


  - Q is a set of "states"


  - T is a set of symbols called the "input alphabet" (terminals)


  - N is a set of symbols called the "stack alphabet" (nonterminals)


  - q0 in Q is the initial state


  - n0 in N is the start symbol


  - F in Q is the set of final states


  - f(q,s) is a function mapping Q x T x N to subsets of Q x N (the
      goto function) (s being a grammar symbol in T union N)


M can be used to recognize exactly a particular deterministic context
free language.


====================================================


I usually use "DFA" to mean "Moore Machine" since automata with output
is much more interesting than not.


A Moore machine ("DFA") is a system (Q, S, O, f(q,s), f(q), s0, F)
where:


  - Q is a set of states


  - S is a set of symbols called the "input alphabet"


  - O is a set of symbols called the "output alphabet"


  - F in Q is a set of final states


  - f(q,s) is a function mapping Q X S to Q (the transition function)


  - f(q) is a function mapping Q to O (the output function)


A moore machine can be used to recognize exactly a particular regular
language.


=====================================================


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]

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