14 Nov 2000 13:08:52 -0500

From: | "Joachim Durchholz" <joachim_d@gmx.de> |

Newsgroups: | comp.compilers |

Date: | 14 Nov 2000 13:08:52 -0500 |

Organization: | Compilers Central |

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

Keywords: | lex, parse |

Posted-Date: | 14 Nov 2000 13:08:52 EST |

<pcj1@my-deja.com> schrieb in im Newsbeitrag:

*> 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)*

I assume that this definition is missing:

- s0 is a set of start states

*> =====================================================*

*>*

*> 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).*

This doesn't sound like it's a mapping function: mapping output symbols

plus a set of DFAs (not their states) isn't going to be an automaton of

any kind.

This definition of a DPDFA sounds awfully like a set of DFAs executing

in parallel; that's a standard model of an NDFA, and judging from your

first post this is not what you mean.

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

This may be my ignorance, but I haven't seen a formal language that's

not either regular, context-free, or context-sensitive. Actually I'm

having difficulties imagining any language that is *not* in one of the

Turing categories, so I'm sceptical that the set of languages recognized

by a DPDFA is not in one of them, so it *should* be equivalent to one of

the four canonical automata (DFA, PDA, what's-it-called and Turing

machine).

Of course, this doesn't mean that a DPDFA isn't an interesting execution

model for one of the language classes.

Regards,

Joachim

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.