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 if 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 accpets tha 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 lateron. Best regards - Jochen Burghardt (talk) 21:01, 1 November 2018 (UTC)