Re: NFA with non-deterministic outputs

George Neuner <>
Tue, 08 Apr 2014 17:37:03 -0400

          From comp.compilers

Related articles
NFA with non-deterministic outputs (2014-04-07)
Re: NFA with non-deterministic outputs (George Neuner) (2014-04-08)
Re: NFA with non-deterministic outputs (2014-04-13)
Re: NFA with non-deterministic outputs (Kaz Kylheku) (2014-04-14)
Re: NFA with non-deterministic outputs (2014-09-09)
Re: NFA with non-deterministic outputs (2014-10-20)
| List of all articles for this month |

From: George Neuner <>
Newsgroups: comp.compilers
Date: Tue, 08 Apr 2014 17:37:03 -0400
Organization: A noiseless patient Spider
References: 14-04-004
Keywords: lex, theory
Posted-Date: 10 Apr 2014 10:20:24 EDT

On Mon, 7 Apr 2014 12:17:44 -0700 (PDT), 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

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.


Post a followup to this message

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