Talk:Nondeterministic finite state machine

From Wikipedia, the free encyclopedia

Mathematics Portal This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.
Mathematics rating:	B Class	High Priority	Field: Algebra
Please update this rating as the article progresses, or if the rating is inaccurate. Click to show/hide comments. Please add to or update the comments to suggest improvements to the article. 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?

Contents 1 About multiple start states 2 Diagram 3 Target Audience 4 Target Audience 5 Inconsistency 6 Example doesn't satisfy the definition of acceptance

[edit] 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)

[edit] 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)

[edit] 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)

[edit] Target Audience

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)

[edit] 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₀ as an element of S.

In the second definition, the author defines which implies s₀ 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)

[edit] 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₀ = {s₀}, therefore, r₀ = s₀.

Therefore, for any input string 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₁ can be {ε}, since the letters x_i are chosen out of the set . 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. 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 ε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:

where

Q = {q₀,q₁}

Σ_ε = {ε,0,1}

T(q₀,0) = {q₁}

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 ε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-ε" should be deleted. The reason is that if one is allowed to arbitrarily add a number of ε'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 ε0 if one is allowed to manipulate an input string of 0 into ε0.

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