NFA with non-deterministic outputs
Mon, 7 Apr 2014 12:17:44 -0700 (PDT)

          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)
| List of all articles for this month |

Newsgroups: comp.compilers
Date: Mon, 7 Apr 2014 12:17:44 -0700 (PDT)
Organization: Compilers Central
Keywords: lex, question
Posted-Date: 07 Apr 2014 23:39:50 EDT

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.

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

- 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

- 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


Post a followup to this message

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