Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #1213

Re: NFA with non-deterministic outputs

Show all headers | View raw

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

Back to comp.compilers | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

NFA with non-deterministic outputs wyse03br@gmail.com - 2014-04-07 12:17 -0700
  Re: NFA with non-deterministic outputs George Neuner <gneuner2@comcast.net> - 2014-04-08 17:37 -0400
  Re: NFA with non-deterministic outputs federation2005@netzero.com - 2014-04-13 11:51 -0700
    Re: NFA with non-deterministic outputs Kaz Kylheku <kaz@kylheku.com> - 2014-04-14 04:34 +0000
    Re: NFA with non-deterministic outputs wyse03br@gmail.com - 2014-09-09 14:26 -0700
      Re: NFA with non-deterministic outputs federation2005@netzero.com - 2014-10-20 15:18 -0700

csiph-web