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

<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

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