Generalized NFA's and their accepted languages

A generalized NFA over an alphabet $\mathrm{\Sigma }$ is a finite state set $Q$ with two distinguished states $s,t\in Q$, $s\mathrm{\ne }t$, together with a label assignment $\lambda :Q\times Q\to \mathrm{Reg}(\mathrm{\Sigma })\mathrm{.}$

We require $\lambda (p,s)=\mathrm{\varnothing }(p\in Q),\lambda (t,q)=\mathrm{\varnothing }(q\in Q),$ so $s$ has no incoming transitions and $t$ has no outgoing transitions.

For states $p,q\in Q$ and a set $K\subseteq Q\setminus \{s,t\}$, let $P_K(p,q)$ be the set of words $w\in {\mathrm{\Sigma }}^{\ast }$ for which there exist an integer $n\ge 0$ and states $p=r_0,r_1,\dots ,r_n=q$ with every intermediate state $r_1,\dots ,r_{n-1}$ in $K$, and a factorization $w=w_1\cdots w_n$ such that each factor belongs to the denoted language of the corresponding edge label: $w_i\in \mathcal{L}(\lambda (r_{i-1},r_i))(1\le i\le n)\mathrm{.}$

When $n=0$, the state list has only $p=q$ and the factorization is empty, so the represented word is $w=\epsilon$.

The language accepted by the GNFA is $L(G):=P_{Q\setminus \{s,t\}}(s,t)\mathrm{.}$

• A GNFA edge label is a regular expression, not a single letter.

• The set $P_K(p,q)$ records words spelled by paths whose intermediate states are restricted to $K$.