11 Nov 2000 10:03:28 -0500

Related articles |
---|

Theory about DFA's and f?lex start states pcj1@my-deja.com (2000-11-09) |

Re: Theory about DFA's and f?lex start states broeker@physik.rwth-aachen.de (Hans-Bernhard Broeker) (2000-11-09) |

Re: Theory about DFA's and f?lex start states chrisd@reservoir.com (2000-11-09) |

Re: Theory about DFA's and f?lex start states pcj1@my-deja.com (2000-11-11) |

Re: Theory about DFA's and f?lex start states cfc@world.std.com (Chris F Clark) (2000-11-14) |

Re: Theory about DFA's and f?lex start states joachim_d@gmx.de (Joachim Durchholz) (2000-11-14) |

Re: Theory about DFA's and f?lex start states ucapjab@ucl.ac.uk (Jonathan Barker) (2000-11-14) |

Re: Theory about DFA's and f?lex start states frank@gnu.de (2000-11-14) |

Re: Theory about DFA's and f?lex start states pcj1@my-deja.com (2000-11-19) |

Re: Theory about DFA's and f?lex start states cfc@world.std.com (Chris F Clark) (2000-11-21) |

[2 later articles] |

From: | pcj1@my-deja.com |

Newsgroups: | comp.compilers |

Date: | 11 Nov 2000 10:03:28 -0500 |

Organization: | Deja.com - Before you buy. |

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

Keywords: | DFA, theory, comment |

Posted-Date: | 11 Nov 2000 10:03:28 EST |

*> [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]

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.