|NFA with non-deterministic outputs email@example.com (2014-04-07)|
|Re: NFA with non-deterministic outputs firstname.lastname@example.org (George Neuner) (2014-04-08)|
|Re: NFA with non-deterministic outputs email@example.com (2014-04-13)|
|Re: NFA with non-deterministic outputs firstname.lastname@example.org (Kaz Kylheku) (2014-04-14)|
|From:||George Neuner <email@example.com>|
|Date:||Tue, 08 Apr 2014 17:37:03 -0400|
|Organization:||A noiseless patient Spider|
|Posted-Date:||10 Apr 2014 10:20:24 EDT|
On Mon, 7 Apr 2014 12:17:44 -0700 (PDT), firstname.lastname@example.org wrote:
>I need to model some inter-operating FSMs and due to the lack of
>details in their specification, modelling them as NFAs seems to be the
>Getting more information about NFAs, it seems that they are mostly used as
>acceptors (no outputs besides accept or no-accept). But I need to model also
>their outputs (transducers?). Besides that, some of these outputs might be
>inputs for the other NFAs.
NFA can model any kind of finite state machine.
>So, here are the questions:
>- is there any example or reference on NFAs issuing non-deterministic outputs?
>It does not need to be a detailed one with all all therorems proved, just the
State transitions [the edges in the graph] are directional and
represent outputs that also are inputs to other states. A transition
can represent anything - not simply "acceptance" - and can represent
"transmission" of data between states. Taking an outgoing transition
represents being in [acceptance of] the *source* state - entry into
the target state remains speculative until it evaluates and accepts
(or rejects) its input.
>- is there any tool that gets the description of a NFA (issuing outputs) and
>translates it to a DFA (deterministic finite state machine), in a format
>simple to parse, to feed other tools
You maybe could hack up something using a lexer tool, but it likely
would be more pain than it's worth ... you really are better off using
a more generalized FSM tool.
A better place to ask would be comp.arch.embedded.
>- is there any reference of multiple NFAs cooperating? I'm particularly
>concerned about inconsistencies between 2 NFAs. For instance, assuming that
>NFA0 has a state Sx where an input a can move to Sy or Sz; and NFA1 has a
>state Si that same input a can move to Sj or Sk; suppose that must be a
>coherence between the non-determinism of both NFAs, such as Sx->Sy in NFA0
>implies in Si->Sj in NFA1. How to model this to assure coherence between
Unfortunately, the only decent references I know of are CS text books
on finite automata. Googling for "nondeterministic finite automata
coordination" might turn up something interesting.
Just as 2 FSM can be combined into 1 bigger FSM, so can 2 NFAs can be
combined into 1 NFA. The best way (if possible) would be to fold Sx
and Si into a single state that outputs coordinated transitions. If
the NFA must remain separate, then Sx and Si somehow must communicate
[message passing] to coordinate their activities.
In short, everything you already know about FSM also applies to NFA.
Return to the
Search the comp.compilers archives again.