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)