Re: NFA with non-deterministic outputs

On Mon, 7 Apr 2014 12:17:44 -0700 (PDT), wyse03br@gmail.com 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
>best approach.
>
>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
>main concepts


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
>NFAs?


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.


George

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