Talk:Finite-state machine

References anyone?

I understand this is pretty much the real deal but like the entire first half of this page has no references. --Sgtlion (talk) 21:49, 13 January 2012 (UTC)

Finite as opposed to infinite?

I don't think there is a wiki page for an Infinite State Machine, so why does this page seem to be distinguishing itself from that page by insisting it is about a FINITE state machine? (In other words, the concept is STATE MACHINE, and the page should be as well.)

I see, upon further reading, that "Turing Machine" is offered as an example of an "Infinite State Machine." I think my criticism is still well founded although no longer well expressed. For all practical applications, "infinite" machines are irrelevant. And even when discussing what a Turing Machine might be able to do, to make the argument that it can solve some problem with an infinite amount of memory is to move the discussion ENTIRELY to the realms of the theoretical--which, of course, is just showing by example that the problem has no actual solution. Engineers learning about state machines don't need to spend any time trying to decide if their problems could or could not be solved if only they had an infinite amount of memory. In practice, when someone shows that a Turing Machine can solve something, an obvious next step is to decide how much memory it would actually use on a given problem, AKA "stack space." Mdlayt (talk) 18:32, 4 September 2012 (UTC) (UTC)

"For all practical applications, "infinite" machines are irrelevant." - not really, but it doesn't matter. The article does not have an obligation to be useful and "practical".

Anyway, there is at least one "practical" use for "infinite memory": Halting problem. It is a practical question, isn't it? And we prove that the question cannot be answered using infinite amount of memory. Thus we know that it cannot be solved using finite memory. And the "finite memory" would be a "red herring" while trying to prove that. --Martynas Patasius (talk) 21:44, 6 September 2012 (UTC)

That is the the reason Turing machines are a stronger computational model. All the things Turing machines can do that state machines can't, like add or multiply arbitrarily large numbers, are due to its unlimited memory.--Chetvorno^TALK 22:31, 6 September 2012 (UTC)

Also, there are a lot of properties of finite state machines that depend on the number of states, which really should be mentioned in this article. For example, a FSM with N states can distinguish between (recognise) no more than N different input sequences, and the output of a FSM with constant inputs will repeat with a period of N or less --Chetvorno^TALK 22:43, 6 September 2012 (UTC).

mathematically FSM

i cant get through the mathematical fsm its just so confusing can anybody explain it in an easy way ? — Preceding unsigned comment added by Syed Faizan jaffri (talk • contribs) 14:58, 1 September 2013 (UTC)

"Turing Machines are not Finite State Machines."

Twice now, my edits had been reverted by those who honestly seem to believe this. They've seemed to had reverted this based upon the assumption that the other models of computations, Turing machines, especially, are a lot more powerful than Finite State Machines and are, therefore, can not be considered Finite State Machines in their own right.

This is in spite of the fact that both pushdown automation and Turing machines uses state machines as the core of their logic. Pushdown automations and Turing machines are, in full effect, both finite state machines, those designed to manipulate a stack-based system and tape-based memory, respectively.

(I must admit that I was maybe wording my edits incorrectly, but if others had realized what I am trying to say, they should've at least put in the effort of actually rewording my post instead of reverting them.) Karjam, AKA KarjamP (talk) 07:55, 8 January 2017 (UTC)

Hi Karjam, my reasons for reverting your edits were the following. There is a hierarchy of automaton classes (cf. diagram in the lead) with each class being able to parse more sophisticated formal languages than those below it; see Chomsky hierarchy for technical details. I think I understand the point you are trying to make, but I disagree - as an analogy, a steering wheel is part of a motor car, yet nobody would argue that it has the same 'automotive capabilities' as a motor car; similarly, although an FSM is part of a TM, the former has less computational power than the latter. - Jochen Burghardt (talk) 19:18, 8 January 2017 (UTC)

In the usual terminology, a Turing machine is not a finite state machine. It it true that a Turing machine is a machine with a finite number of states, but being a "finite state machine" means there is no other form of memory apart from knowing the current state. Turing machines have additional memory in the form of the tape, so they are not finite state machines. — Carl (CBM · talk) 23:04, 8 January 2017 (UTC)

First off, my gripe's not about the attempt at mentioning Hierarchical state machines. It's about the reversion of the attempt to refer to the other automas as types of state machines.

Second, where's your source that claims "usual terminology"? Just because Turing machines uses tape memory doesn't make them less of state machines, the same with pushdown automations and their stacks. Just because something has memory does not make anything less of a state machine. If it uses a finite amount of states that can be transitioned in-between, it's a finite state machine. Simple as that.

(Besides, I have at least one application of state machines in mind which effectively requires the usage of memory in order to keep track of things, and that would be video games.)

Karjam, AKA KarjamP (talk) 07:04, 9 January 2017 (UTC)

"It it true that a Turing machine is a machine with a finite number of states": No, that is not true. By definition, a Turing machine has an infinite amount of memory, in the form of an infinitely long tape, which it can access (read or write) by moving back and forth along the tape. Since a Turing machine can be in any position along that infinite tape, it can be in any state; hence they do not have a finite number of states.

Of course infinite memory does not exist in practice: Turing machines are theoretical constructs.

This may also deal with Karjam's objection that "Just because Turing machines uses tape memory doesn't make them less of state machines": Turing machines are not finite state machines precisely because their tape is not *finite*.) Mcswell (talk) 18:04, 18 April 2019 (UTC)

For a reference, any textbook on Formal Language Theory will do. - Jochen Burghardt (talk) 19:41, 9 January 2017 (UTC)

Agree with Jochen Burghardt and CBM. A Turing machine has an infinite amount of memory, so it is not a Finite State Machine. --Chetvorno^TALK 19:53, 9 January 2017 (UTC)

"Any textbook on Formal Language Theory" won't fly here on Wikipedia. I meant a specific reference, one which specifically states they're not Finite State Machines. You know, something that conforms to WP:Reliable. That policy's here for a reason, for if it weren't for policies such as that, I could say anything and you can't prove it. Wikipedia's reputation as an unreliable source among universities and the like would be completely unfounded.

I don't want to repeat myself on what I said about Turing machines being state machines. Let's just say that just because it manipulates memory doesn't make them any less of a state machine. Heck, you can even plan Turing machines using diagrams precisely because its logic happens to be run by a state machine. What you guys are not understanding is that I'm not saying a pure Finite State Machine, that is, one not designed to manipulate a tape or stack, is better than those that are designed to do so, in other words a Turing machine and a pushdown automation, respectively.

What makes a Turing machine would be a state machine and a piece of tape. What makes a Pushdown automation would be a a state machine and at least one stack. What makes a pure state machine happens to be just the state machine itself. It has limited memory not because it's unable to, but because it's not designed to handle something as such. Under your logic, a finite state machine designed to manipulate an infinite tape would be a Turing machine, not a state machine.

Karjam, AKA KarjamP (talk) 05:01, 10 January 2017 (UTC)

Karjam, you are seriously confused about this topic; your use of "pure" should be a hint that something is amiss. It's not up to us to find reliable sources to refute you, but it is up to you to find reliable sources that support your edits. You are not going to find sources that say a FSM is as powerful as a PDA or TM. Nobody disputes that a Turning machine is a finite state machine with an infinite tape. That finite state machine can be configured as an interpreter to make a universal Turing machine: something that can simulate any finite state machine and any Turing machine. You cannot make a finite state machine that does that; it cannot simulate a machine that has more states. Nobody is going to dispute that a Turing machine is not "state machine"; it has states and transitions from one state to the next. There is a huge distinction in that TMs and PDAs are infinite state machines rather than finite state machines. (CBM is wrong here; what is written on the tape is state information.) I also won't dispute that my crufty laptop with 8 GB of RAM and 1 TB of disk is a finite machine; it does not have infinite memory, so it must be a FSM even though most consider it more of a Turing machine than a vending machine. The computational models are abstractions. For most problems, the infinite tape only needs to be big enough; one can never use all of an infinite tape anyway. My FSM laptop has most of the benefits of a TM (it can simulate a lot of useful TMs) as well as its ills (such as a computationally infeasible halting problem). Glrx (talk) 05:59, 10 January 2017 (UTC)

Although the information on the tape does affect the overall state of the computation in the general sense of "state", it is common in the literature to use the term "state" of a Turing machine to refer to current location in the table of states only, and use some other term such as "configuration" or "instantaneous description" instead of "state" to refer to the combination of that state, the tape contents, and the location of the read/write head. As in [1] or Sipser's text. — Carl (CBM · talk) 12:34, 10 January 2017 (UTC)

Agreed, but your, Glrx's and Burghardt's point remains. A Turing machine contains a FSM, and the capabilities of a Turing machine include those of a FSM, but a Turing machine also includes other parts and has additional capabilities, so a Turing machine is not a FSM. --Chetvorno^TALK 21:10, 10 January 2017 (UTC)

Alright, guys. I have a hunch that we may be misunderstanding each other. What Chevorno says is a clue: "A Turing machine contains a FSM, and the capabilities of a Turing machine includes those of a FSM, but a Turing machine also includes other parts and has additional capabilities, so a Turing machine is not a FSM.

It's a State machine that powers a Turing machine, like what Chetvorno says. When I said a "pure Finite State Machine", I meant state machines on their own, not state machines that are used in conjunction with other features to become some other automa (i.e., combined with a tape to become a Turing machine, or combined with a stack to become a Pushdown automation).

Of course, they're not Finite State Machines, for if they are, they wouldn't have those extra capabilities that make them a Turing machine or a Pushdown Automation. That's what you guys are saying, right? Correct me if my line of reasoning seems to be wrong.

Karjam, AKA KarjamP (talk) 12:17, 11 January 2017 (UTC)

External links modified

Hello fellow Wikipedians,

I have just modified one external link on Finite-state machine. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

• Added archive https://web.archive.org/web/20140821054702/http://www.iam.unibe.ch/~run/talks/2008-06-05-Bern-Jonczy.pdf to http://www.iam.unibe.ch/~run/talks/2008-06-05-Bern-Jonczy.pdf
• Added {{dead link}} tag to ftp://reports.stanford.edu/pub/cstr/reports/cs/tr/71/190/CS-TR-71-190.pdf

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 18 January 2022).

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 01:23, 1 October 2017 (UTC)

A or an?

The article currently has both "a FSM" and "an FSM". Only one should be used. Which one is correct depends on how it's pronounced by those working in the field -- do you say "an eff-ess-em" or do you expand it in full? 195.157.65.228 (talk) 15:28, 5 May 2018 (UTC)

both pronunciations are used; that's why there's confusion. Glrx (talk) 21:51, 25 May 2018 (UTC)

Acceptor issue

Why, when referencing figure 4, does the the acceptor section say that state 7 is the only accepting state? It says accepting states can either accept or reject input, and in the figure four other states can accept or reject the input. So aren't all states, except state 6, accepting? — Preceding unsigned comment added by 184.2.141.98 (talk) 19:19, 2 February 2021 (UTC)

The transition function of NFAs and inconsistency across articles

About the transition function of NFAs, a paragraph at the formal definition section here reads:

δ is the state-transition function: δ : S × Σ → S (in a nondeterministic finite automaton it would be δ : S × Σ → P(S), i.e.  would return a set of states);

At the article on NFAs, however, the transition function is described as δ : S × (Σ ∪ {ε}) → P(S), not δ : S × Σ → P(S).

This is an inconsistency, correct? Which one is right? Qwertesque (talk) 13:23, 13 March 2024 (UTC)

As usual in mathematics, there are different versions around. Two sources can prevent a finite automaton from being deterministic: (1) having different transition from the same state s for the same input symbol x∈Σ, and (2) allowing the automaton to change its state spontaneously at any time, without reading an input symbol. Sometimes, both (1) and (2) are allowed. The definition δ : S × Σ → P(S) is used when (1) is allowed, but (2) is not; P(S) denotes the set of all sets of states (i.e. the follow-on state of a transition from s and x may be chosen arbitrarily from the set δ(s,x)). The definition δ : S × (Σ ∪ {ε}) → P(S) is used when (1) and (2) are allowed; ε denotes the empty string (i.e. no input read). - I agree this should be made clear in the article. - Jochen Burghardt (talk) 14:01, 14 March 2024 (UTC)

Thank you very much for clarifying.

Perhaps we should move "in a nondeterministic finite automaton it would be δ : S × Σ → P(S), i.e. would return a set of states" to its own paragraph below and modify it to further clarify the case of the transition function. We could write as follows:

"In a nondeterministic finite automaton, the transition function differs. It can be described as etiher δ : S × (Σ ∪ {ε}) → P(S), with ε denoting an empty string, if the automaton is allowed to change its state without reading an input symbol or δ : S × Σ → P(S) if it is not. Either way, the codomain of the transition function for nondeterministic finite automata is the set of all sets of S instead of the set S, i.e. the function returns a set of states instead of a single state." Qwertesque (talk) 23:48, 14 March 2024 (UTC)