Let us assume, we have a FSM (to be precise, an epsilon-NFA) in which I've got redundant structures.
I am looking for a framework that allows to factor out the redundant part into some kind of subautomaton, respectively a more canonical representation and naming of this kind of NFA.

As illustration I've got the following NFA as example (It is just an example. I don't want to discuss, whether it could be minimized or designed more intelligently.)

NFA with Redundancies

I imagine a representation like this:

enter image description here

What I am specifically looking for is the possibility, to research scientific ressources and algorithms, to basically do this kind of "refactoring", which help me argue that though the grammar I'd extract from the result may be context-free, the language is still regular (since it is naturally identical to the orignal language accepted by an NFA).

So ideally, the accepted language class of the kind of automaton is regular.
Basically nothing more than a compact representation of highly redundant NFAs.


2 Answers 2


You may want to have a look at SCCharts, which extend FSMs (a.o.) with hierarchy and named sub-machines.

  • $\begingroup$ Thank you. Though it is not what I was looking for (I edited the question to be more concise), the linked project seems to be very interesting. In fact, I was looking for something like that (though not in this question!) $\endgroup$
    – derM
    Commented Sep 14, 2023 at 8:33
  • $\begingroup$ That appears to be a form of statecharts. There are many more tools/techniques like this. I'm not familiar with them, but I've seen quite a few. $\endgroup$ Commented Sep 14, 2023 at 9:00
  • 1
    $\begingroup$ @reinierpost yes, Harel's StateCharts are a precursor formalism. Allegedly, before 2000 there were already 95 published semantics for them :) $\endgroup$
    – Kai
    Commented Sep 14, 2023 at 9:56
  • 1
    $\begingroup$ I was brought up with coloured Petri nets - basically, statecharts with the WTF factor of Petri nets. $\endgroup$ Commented Sep 14, 2023 at 11:23

To answer this conclusively, we'd need to know more about how you intend to describe your NFAs with (named?) sub-NFAs.

If the directed graph obtained by having your (sub-)NFAs as nodes and your dashed arrows as directed edges has no cycles, then a copy semantics would necessarily give a finite traditional NFA and regularity of the language would follow.

If however you allow a collection of named NFAs with references to NFA names then regularity is at risk. For ease of expostion I'm borrowing from regular expressions here. Imagine a syntax for a list of declarations such as $N = \mathsf{a}N\mathsf{b} | \epsilon$ where $N$ is such a name. We'd have $L(N) = \{~\mathsf{a}^n\mathsf{b}^n~|~n\in\mathbb{N}~\}$, which is of course not regular.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.