Linked Finite State Machine

Question

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.)

I imagine a representation like this:

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.

Answer 1

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

Answer 2

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.