Talk:Nondeterministic finite automaton

About multiple start states

A number of books describe only one start state. Does that make any difference?

If you have multiple start states, then you might find the concept of a semiautomaton more useful. linas 20:21, 19 May 2007 (UTC)

Diagram

This page is well-done, but I think it'd be nice if the diagram demonstrated the nondeterminism a little better, by having two edges with the same label coming out a single node somewhere. Deco 21:37, 12 Nov 2004 (UTC)

Target Audience

While this article seems very succinct, the content is very much targeted towards computer scientists. As a non-computer scientist having read both 'Deterministic finite state machine' and 'Nondeterministic finite state machine' I still don't understand either explanations. I'm guessing nondeterministic finite state machines refers to computer algorithms which perform 'trial and error' calculations to a finite problem in order to derive a finite set of solutions. However, this certainly isn't clear from the article so I may be way off. Anyhow, can I encourage someone who does understand this subject to consider pitching it at a much wider audience. --angusj 00:32, 17 September 2005 (UTC)

Is it better now? linas 21:46, 19 May 2007 (UTC)

Perhaps non-Computerists have trouble focusing on the notion of explicit blurring? The algorithm is explicitly not determined so we can prove theorems and think about these machines in a general way without getting entangled in details of particular implementations.

No that is incorrect; that is not what NFA's are for. In particular, NFA's do have particular details that cannot be ignored. linas 21:48, 19 May 2007 (UTC)

BTW a very good introduction into the concept of NFA is the original 1959 article by Rabin and Scott. They got the Turing award for this, and the award citation explicitly mentions their good explanations. Surely a good source of inspiration to improve the article Hermel (talk) 13:03, 7 May 2009 (UTC)

While not a "computer scientist" nor a programmer, I am the geekiest person in my offline world and have been a "power user" for 25+ years. And after spending twenty minutes reading these related articles have not a clue what they're trying to say. Would it be possible to extend the "car radio" example in the main article? Or adapt another one? If this were of greater interest to me, I'm sure I could do more research, but feel that WP should at least have given me enough information to decide whether that would be worth my time or not, and it didn't. HansBKK 2011-12-24T09:33+7 — Preceding unsigned comment added by 58.8.99.196 (talk) 02:34, 24 December 2011 (UTC)

Inconsistency

There is an inconsistency in the two definitions in this Article:

"A nondeterministic finite state automaton (NFA) is a 5-tuple, (S, Σ, T, s0, A), consisting of

a finite set of states (S)

a finite set of input symbols (Σ)

a transition function (T : S × (Σ ∪{ε}) → P(S)).

an initial (or start) state s0 such that s0 ∈ S

a set of states A distinguished as accepting (or final) states (A ⊆ S) where P(S) is the power set of S, ε is the empty string, and Σ is the input symbol alphabet.

Let M be an NFA such that M = (S, Σ, T, s0, A), and X be a string over the alphabet Σ. M accepts the string X if there exist both a representation of X of the form x1x2 ... xn, xi ∈ (Σ ∪{ε}), and a sequence of states r0,r1, ..., rn, ri ∈ S, meeting the following conditions:

r0 ∈ s0

ri ∈ T(ri-1, xi ), for i = 1, ..., n

rn ∈ A. "

In the first definition, the author defines $s_{0}$ as an element of S.

In the second definition, the author defines $r_{0}\in s_{0}$ which implies $s_{0}$ is a subset of S.

--CBKAtTopsails 18:35, 27 April 2007 (UTC)

This appears to have been fixed in the current article. linas 21:48, 19 May 2007 (UTC)

Example doesn't satisfy the definition of acceptance

"The following example explains a NFA M, with a binary alphabet, which determines if the input contains an even number of 0s or an even number of 1s.

M = (S, Σ, T, s0, A) where

Σ = {0, 1},

S = {S0, S1, S2, S3, S4},

s0 = {S0},

A = {S1, S3}, and

The transition function T can be defined by this state transition table:

0 1 ε 

S0 {} {} {S1, S3}

S1 {S2} {S1} {}

S2 {S1} {S2} {}

S3 {S3} {S4} {}

S4 {S4} {S3} {}

The state diagram for M is:"

In this example, the author defines $s_{0}=\{s_{0}\}$, therefore, $r_{0}=s_{0}$.

Therefore, $T(r_{0},x_{1})=\varnothing$ for any input string $w=x_{1}x_{2}\cdots x_{n}$ according to the transition function defined above unless $w=emptystring$.

It appears that this machine can only accept the empty string according to the above definition.

--CBKAtTopsails 19:57, 27 April 2007 (UTC)

No, that's not right. The point is that $x_{1}$ can be $\{\epsilon \}$, since the letters $x_{i}$ are chosen out of the set $\Sigma \cup \{\epsilon \}$. That is, any of the "letters" $x_{i}$ can be "empty". I tried to emphasize this in the article; is it clear now? linas 21:55, 19 May 2007 (UTC)

My question to you is the following:

If w is not empty string then there must be an x_i$\neq \epsilon$. In this case, we would have x₁ x₂...x_n = x_i....x_n. If I pass the string w = x_i....x_n through your machine, it is still going to rejected by it unless you are going to tell me, "No,no,no,...,you've got to attach an empty string to it before you can do that."

Is this a ground rule that you want to set for the theory of NFA's and why? --CBKAtTopsails 18:35, 21 May 2007 (UTC)

No,no,no,...,you've got to attach an empty string to it before you can do that. Actually, you may have to put empty strings between every pair of letters, and also at the end. You may have to put any number of empty strings in there. Yes, this is a ground rule for the "NFA with epsilon moves". Why? Because someone (probably Rabin or Scott) said "gee that would be neat". They then showed that, for every NFA-epsilon, there is another, equivalent NFA without epsilon moves. And vice-versa. So its your pick as to which you prefer. The reason for defining both is that some theorems are easier to prove for one, and some for the other. But since they're equivalent, it doesn't much matter. Similarly, for each NFA, there is an equivalent DFA, and vice-versa, so you could just work with only DFA, if that makes you happier. linas 14:05, 1 June 2007 (UTC)

I am confused about your argument here.

Let's stick with the NFA-epsilon model.

What are the specific rules with regard to when and where in the string and how many epsilons should be added before one can pass an input string to a machine to determine if the string is accepted by the machine?

In the example you used in the Article, obviously, if I pass the string 11 to the machine, it will be rejected (under the original definition but not the revised definition). However, if I convert it to $\epsilon$11, it will be accepted.

However, there are some other situations in which the above rule has to be reversed.

Let's consider the following NFA:

$N=(Q,\ \Sigma _{\epsilon },T,q_{0},\{q_{1}\})$

where

$Q=\{q_{0},q_{1}\}$

$\Sigma _{\epsilon }=\{\epsilon ,0,1\}$

$T(q_{0},0)=\{q_{1}\}$

$T(q_{0},x)=\phi \ if\ x\neq 0$

$T(q_{1},x)=\phi \ \forall x$

This simple machine is supposed to accept only the string 0 and reject any thing else. In fact, if I pass the string 0 to the machine, it will be accepted. However, if I follow the above rule (as used in your example) to convert 0 to $\epsilon$0, it will be rejected.

My point, therefore, is the following:

You must have a set of standard rules to be used in all situations. Otherwise, you are going to end up with different results when you do it arbitrarily.

--CBKAtTopsails 19:39, 1 June 2007 (UTC)

I feel that there is, in general, a lack of rigorous mathematical treatment in the subject of theoretical computer science and as a result, technical errors, sometimes, can be found all over the place. I can volunteer to add some mathematical features to this Article and do it in such a way that it will not affect the main theme of the Article. I believe that this is going to be beneficial in 2 ways:

(i) Understanding the mathematical process can help one understand the subject more thoroughly.

(ii) By going through the logical arguments in the mathematical process, one can minimize the chance of making mistakes, identify the problems and demonstrate why an error is an error.

--CBKAtTopsails 19:39, 1 June 2007 (UTC)

"In particular, note that some of the letters x_i can be {ε}; they are chosen not from Σ alone, but from Σ ∪{ε}.".

The above statement quoted from the section "Properties of NFA-$\epsilon$" should be deleted. The reason is that if one is allowed to arbitrarily add a number of $\epsilon$'s to an input string, you can end up with a situation in which an NFA accepts and rejects the same string at the same time.

The above example clearly shows that an NFA can be constructed to accept the string 0 but reject the string $\epsilon$0 if one is allowed to manipulate an input string of 0 into $\epsilon$0.

--CBKAtTopsails (talk) 18:33, 20 November 2007 (UTC)

Infinite number of states

I think that a technical discussion about automata with an infinite number of states is misplaced in an article about NFAs. I cut and pasted the part in question and place it here:

For non-deterministic automata with a countably infinite set of states, the powerset construction gives a deterministic automaton with a continuum of states (since the powerset of the countable infinity is the continuum: $2^{\aleph _{0}}=\aleph _{1}$). In such a case, the set of states must be endowed with a topology in order for the state transitions to be meaningful. Such systems are studied as topological automata.

If you feel that passage should be reinserted, please argue. 23:09, 6 May 2009 (UTC) —Preceding unsigned comment added by Hermel (talk • contribs)

I think a better place for this is powerset construction. However, I wouldn't mind seeing this article merged into a larger article on nondeterministic state machines in general. Dcoetzee 23:12, 6 May 2009 (UTC)

I think the concept is both of central importance and there is enough content to justify an article on its on right. I think discussing too many variants and generalizations will disturb most readers.Hermel (talk) 13:03, 7 May 2009 (UTC)

Formal vs Informal usage

This page is entirely a discussion of the formal theory of NFAs. But in the programming world when people talk about regular expression engines they use the term NFA informally . For example PCRE is described as an NFA engine, even though it is strictly not.

Shouldn't the article at least acknowledge that informal usage in industry differs from what is being discussed? —Preceding unsigned comment added by 72.10.62.12 (talk) 20:12, 11 May 2011 (UTC)

Move discussion in progress

There is a move discussion in progress which affects this page. Please participate at Talk:Deterministic finite-state machine - Requested move and not in this talk page section. Thank you. —RM bot 15:20, 25 November 2011 (UTC)

unnecessary abbreviations, NDFA and NDFSM

I don't think that reference to abbreviations "NDFA" and "NDFSM" is needed, because rest of the article and wikipedia does not refer to the abbreviations. If User:Urhixidur doesnot object then I will remove it. Ashutosh Gupta (talk) 08:03, 21 April 2012 (UTC)

LaTeX?

This page uses symbols that don't render properly in IE8 running on WinXP. Any thoughts/objections regarding switching to LaTex? Morfusmax (talk) 18:53, 28 May 2013 (UTC)

An error in the article?

It sounds to me like a nondeterministic finite automaton would not be deterministic, that is, not a deterministic finite automaton. But according to the article, "every DFA is also an NFA", meaning that some NDAs are in fact DFAs. This sounds like a contradiction to me, and I think that DFAs and NFAs should have no intersection. "Every DFA is also an FA" sounds more reasonable to me. Is this an error in the article or is "nondeterministic finite automaton" a misnomer? —Kri (talk) 11:48, 25 May 2015 (UTC)

I admit that this terminology is confusing; but it is taken from Hopcroft+Ullman (1979, e.g. 1st sentence on p.22: Since every DFA is an NFA,...). An NFA is allowed to contain nondeterministic transtions, but is not required to. This is similar being to a rational number: having a denominator >1 is allowed, but not required, in the latter case it is also an integer number. The class of automata that are required to contain nondeterministic transtions is not interesting by its own; for example, it doesn't have convenient closure properties. - Jochen Burghardt (talk) 17:40, 25 May 2015 (UTC)

Okay, I understand that the article is correct and that it can in fact be called an NFA even though it may be deterministic, but I don't agree that the case of rational numbers and integers is a very good analogy as "rational" doesn't have anything to do with whether the number is an integer or not, whereas (in my opinion) "nondeterministic" clearly states that the FA is not deterministic. A better analogy would instead be "irrational", which clearly states that the number is not rational (which is also true), or "nonnegative", which states that the number is not negative (which is also also true).

Why not just call it a "finite automaton"? (Since the term NDA apparently doesn't specify whether the FA is deterministic or not anyway.) I see that the Wikipedia article for this term redirects to finite-state machine. So is there any difference between an NDA and an FSM? —Kri (talk) 20:00, 25 May 2015 (UTC)

Inconsistency with ε-moves

The introduction states an NFA is not required to read an input symbol for each state transition. Such transitions without reading an input symbol are ε-moves. However, later in the introduction ε-moves are considered to be an extension to NFAs (with a link to the separate article Nondeterministic_finite_automaton_with_ε-moves). The formal definition also does not support ε-moves.

This change introduced the statement without extending the formal definition or merging with Nondeterministic_finite_automaton_with_ε-moves. I think the first paragraph of the introduction can simply be changed to:

In automata theory, a finite state machine is called a deterministic finite automaton (DFA), if each of its transitions is uniquely determined by its source state and input symbol. A nondeterministic finite automaton (NFA), or nondeterministic finite state machine, does not need to obey these restrictions. In particular, every DFA is also an NFA. --PapaNappa (talk) 14:57, 26 August 2015 (UTC)

See merge proposal, below. QVVERTYVS (hm?) 17:07, 21 October 2015 (UTC)

Proposed merge with Nondeterministic finite automaton with ε-moves

The current setup of these two articles suggests that unqualified "NFA" means "NFA without ε-transitions". I doubt that it does; e.g., how many descriptions of Thompson's construction care to make the distinction? Since NFA might mean both kinds of automaton depending on context, I think we should merge. QVVERTYVS (hm?) 17:06, 21 October 2015 (UTC)

I totally agree. I think we should unify the formal definition, and keep both examples. PapaNappa (talk) 12:52, 24 November 2015 (UTC)

Assessment comment

The comment(s) below were originally left at Talk:Nondeterministic finite automaton/Comments, and are posted here for posterity. Following several discussions in past years, these subpages are now deprecated. The comments may be irrelevant or outdated; if so, please feel free to remove this section.

ToDo: Article needs: A demonstration of how NFA and NFA-epsilon are equivalent (this is a fairly simple demonstration) More historical background: Rabin and Scott came up with this; why? Some discussion of why its useful: why work with this instead of DFA's?

Last edited at 01:42, 1 January 2012 (UTC). Substituted at 20:09, 1 May 2016 (UTC)

First example and diagram could be improved for newbies

I am unable to understand the first example and diagram in this article. I think that additional information might make it easier for people that are new to NFA to understand the example. Answers to some or all of the following questions would, IMO, be helpful:

• When the state is p and input is 1, how does M determine what the next state will be? Specifically, why does the first '1' cause state sequence 1 to transition to state q while the same input causes state sequence 2 to stay in state p?
• What is the meaning of the question marks in the bottom table?
• Is there additional information involved that is not mentioned in the example? In particular, is the word "1011" accepted because (a) the NFA knows that inputs always contain four characters, (b) the NFA is somehow informed that the final '1' is, in fact, the final character of the word, or (c) the NFA receives additional input (e.g. a NUL (or EOS)) input that is not shown in the diagram or listed in Σ?
• What is the ε-transition discussed in the final sentence of the example? Note that this term is not mentioned until later in the article so the example appears to be using knowledge that has not yet been introduced to the reader.

[Context: I have experience using FSMs but this article is the first time I've encountered nondeterministic FSMs.] Jvasil (talk) 16:20, 1 November 2018 (UTC)

I think the problem is that the lead and the Informal introduction fail to given an intuitive impression on how an NFA works. I'm unable to fix this ad hoc, so I'll just try to answer your questions for now.

• 'Nondeterministic' means that M is allowed to choose arbitrarily among the transitions that are available in the current state. So when state is p and input is 1, M is allowed to stay in p, or to proceed to q. Contrary to what the Informal introduction says, a word w is accepted by M if, and only if, there is some "lucky run" for w, i.e. a run where the choices made by M take it to an accepting state. State sequence 1, 2, and 3 show different sequences of choices made by M on the same input word "1011". Sequence 3 is a lucky run that ends in the accepting state q, therefore, "1011" belongs to the language of M. - While this concept often appears nonsensical from a practical point of view, it has been very useful in theoretical investigations.
• The "?" mean that in the current state, no applicable transition exists for the current input symbol. In such a case, the automaton has run into a "dead end". It cannot proceed and eventually reach an accepting state in this run. Nevertheless, the word may possibly be accepted by another run.
• None of the information you mentioned is available to M. Just the word is fed into M symbol by symbol until its end, and after that, M′s current state is inspected. If it is an accepting state, the word is in M′s language, else, start all over again to retry. If eventually every possible state sequence has been tried in vain, the word is known not to be in M′s language.
• An ε-transition allows M to change the state without reading a symbol ("ε" usually denotes the empty string). In the second picture, two ε-transitions leave the leftmost state S₀. So when the automaton is in state S₀, it has to choose whether to proceed to S₁ or to S₃; but it doesn't read an input symbol. - By the way, this illustrates a strength of the NFA concept: it is obvious that the automaton just accepts the union of the languages accepted by the upper sub-automaton (consisting of S₁, S₂) and the lower one (S₃, S₄), as described in the example down there. (The general scheme for an NFA accepting a language union is sketched in the third picture.) Without using nondeterminism and in particular ε-transitions it is not that easy to given an automaton for the union. - As a side remark: when an automaton contains a cycle consisting only of ε-transitions, the set of all possible runs becomes infinite; in that case trying out all possibilities is no longer practically feasible. Given an NFA for a practical application, you would transform it anyway into an equivalent DFA, and implement the latter.

I hope that helps somewhat; feel free to ask more questions. I think your above questions were very helpful to improve the article later on. Best regards - Jochen Burghardt (talk) 21:01, 1 November 2018 (UTC)

Thank you very much for the detailed response--it helped me quite a bit. I worked through the example and it seems to me that there should be a fourth sequence:

State sequence 4: p p p p p

It's true that the article says the table contains Some possible state sequences but if it only takes one more row to show all sequences then it is probably worthwhile to add the final one (from an education POV). On the other hand, perhaps there are additional sequences that I haven't identified??

Your statement that None of the information you mentioned is available to M doesn't quite jibe with the word is fed into M symbol by symbol until its end. It seems to me that this is the same as informing M that it has reached the end of the input (my option b).

Is the use of $\emptyset$ in the state table a standard convention used by people working with NFAs? Could they be replaced by a new state, r?

State	0	1
p	{p}	{p,q}
q	{r}	{r}
r	{r}	{r}

In the example, this would cause the sequences that end in '?' to end in r. This seems preferable to me since r is explicitly defined. I guess that the null state is an OK shorthand as long as everyone understands that:

• $\emptyset$ is not an accepting state
• $\emptyset \times \Sigma \rightarrow \emptyset$.

I realize that it is sometimes hard to come up with an example that both illustrates the concept AND is easy to understand. But, it would be nice if the example made more use of the nondeterministic nature of the NFA and couldn't be simplified to:

State	0	1
p	{p}	{q}
q	{p}	{q}

Finally, my comment about the ε-transition was meant to point out that this term was being used in example 1 which is before the term is defined, later in the article. Unless I've missed something, there are no ε-transitions in example 1.

Thanks again for your help! Jvasil (talk) 16:22, 2 November 2018 (UTC)

A quick reply:

• There is at least a 5th sequence, viz. "ppq?". But I think these are all, and it may indeed be a good idea to list them completely.
• In some sense, you are right, information about the word end is used. However, it is kept outside of M, so M can't let it choices depend on it. It is just a matter of when you look at M′s current state. By analogy, in a car you just look at the mileage counter when you arrived at your goal, in order to learn the distance you drove. You don't have to push a "I arrived" button to tell the car and to get the distance in reply.
• "$\emptyset$" in the state table denotes the empty set (of states). It is not the name of a state, hence your suggestions "$\emptyset \times \Sigma \rightarrow \emptyset$" etc. don't make sense. Adding another state r would of course be possible, but that would yield a different automaton (accepting the same language). I prefer no to add an r, so that the possibility of a "dead end" can be demonstrated. (It should, however, be explained in the text.)
• It seems you found a deterministic version ("DFA") accepting the same language and not larger. Maybe the automaton shown in File:Relatively small NFA.svg would be a better replacement for example 1. Its corresponding DFA (shown in File:Big DFA.svg needs at least 16 states, thereby illustrating another advantage of NFAs, viz. conciseness.
• You are right, there are no ε-transitions in example 1.

Best regards - Jochen Burghardt (talk) 18:47, 3 November 2018 (UTC)

Closure Properties

The opening sentence, "NFAs are said to be closed under a (binary/unary) operator if NFAs recognize the languages that are obtained by applying the operation on the NFA recognizable languages", is too hard to parse.

I also challenge its truth. Do people actually write thus?

The next statement also seems dubious: "Since NFAs are equivalent to nondeterministic finite automaton with ε-moves (NFA-ε), the above closures are proved using closure properties of NFA-ε." How is the alleged closure under negation proved? Via conversion to a DFA? --RichardW57m (talk) 12:31, 28 April 2022 (UTC)

As for the opening sentence, I made an alternative suggestion; feel free to improve or revert with a justification.

As for NFA-ε, Hopcroft+Ullman (1979) prove the equivalence of DFA and NFA (Thm.2.1 p.22), that of NFA and NFA-ε (Thm.2.2 p.26), and that of NFA-ε and regular expressions (Thm.2.3 p.30 and Thm.2.4 p.33). Somewhat later, they prove the closure properties of regular expressions (Thm.3.1-3.3 p.59). This confirms the challenged sentence in the article. Maybe, the section "Closure properties" should follow H+U's way of presentation, and just refer to the closure properties of regular expressions? - Jochen Burghardt (talk) 18:09, 28 April 2022 (UTC)

I believe RichardW57m's point is that NFAs are not "closed under" any operations, it's the class of languages accepted by NFAs that is closed under the operations. I made an edit. An alternative presentation would be to discuss "constructions" on NFAs, rather than closure properties. Caleb Stanford (talk) 21:24, 28 April 2022 (UTC)

NFA-epsilon

The article is a bit of a mess; as a recent edit points out, the proof that NFA-epsilon are equivalent to NFA is wrong because of there being only one initial state. We should probably edit to allow multiple initial states throughout the article. Caleb Stanford (talk) 21:27, 28 April 2022 (UTC)

It is sufficient that an NFA can have multiple final states. If the start state is final, it will recognize the empty string. Also, I just checked our formal definition against the prose in Hopcroft and Ullman 1979 (DFA p.16, NFA p.19), and found they agree. Hence, the proof theorem is right, or H+U are wrong. However, I didn't yet check if the proof in the article is right. - Jochen Burghardt (talk) 14:10, 29 April 2022 (UTC)

The proof in question is at Nondeterministic finite automaton#Equivalence to NFA. The set of initial states of the new automaton is listed as $E(q_{0})$ (the epsilon-closure of $q_{0}$), which is invalid because it has to be a single state, not a set. I think the fix is to make a new "special" initial state that is accepting if the automaton should accept the empty string, and with transition as appropriate that are then epsilon-closed sets. I don't think it's possible to fix it without adding a new initial state, because there may be multiple initial states that are epsilon-reachable from the old initial state, and we can't just pick one and start modifying it and adding new transitions from it. Caleb Stanford (talk) 01:06, 30 April 2022 (UTC)

I just read that section, and I agree that the proof is flawed, due to the reason you gave above. Since the proof is unsourced, anyway, I suggest to replace it by Hopcroft and Ullman's proof. If you don't object, I could do this in the next days. - Jochen Burghardt (talk) 08:02, 30 April 2022 (UTC)

No objection, that would be great! Thanks Caleb Stanford (talk) 16:39, 30 April 2022 (UTC)

I started to do so, but got stuck at the last case of the proof of $\delta '^{*}(q_{0},w)\cap F'\neq \{\}\;\Rightarrow \;\delta ^{*}(q_{0},w)\cap F\neq \{\},$ cf. the ((clarify)). It seems that I have to think about this in more detail tomorrow. - Jochen Burghardt (talk) 19:47, 30 April 2022 (UTC)

I think you will need to add a new initial state, as I said in my previous comment. The problem is, currently, you are labeling the initial state $q_{0}$ as final or not depending on whether or not the empty string is accepting. But this could have the side effect of causing other strings to be accepted, that were not accepted before, since the initial state may not be accepting in the original automaton. So you have to define $M'=(Q\cup \{q_{new}\},\Sigma ,\delta ',q_{new},F'\}$ instead of what you have currently. Alternatively you could first construct a machine with an initial state with no incoming transitions. Caleb Stanford (talk) 02:58, 1 May 2022 (UTC)

It is somewhat cleaner (and more natural) to allow multiple initial states and initial final states simply baked into the definition of NFA. That would be my preference for the article. Caleb Stanford (talk) 02:59, 1 May 2022 (UTC)

I'm still scuffling with the Hopcroft.Ullman.1979 proof. You may be right that allowing sets of initial states is necessary, but in this case, I wouldn't have a source that I could paraphrase.

Looking in the 2nd edition of Hopcroft.Ullman.1979, viz. Hopcroft.Motwani.Ullman.2003 (which might still be available online), I found they prove (in sect.2.5.5. on p.77) that for a given NFA-epsilon E, an equivalent DFA D can be constructed. The states of D are the epsilon closures of stets of E. This seems to come close to your suggestion, while on the other hand inheriting much from the usual NFA-to-DFA powerset construction. - Jochen Burghardt (talk) 16:16, 2 May 2022 (UTC)