We are currently working on new rules for what content should and shouldn't be allowed on this website, and are looking for feedback! See Esolang:2026 topicality proposal to view and give feedback on the current draft.
Talk:Finite-state automaton
Jump to navigation
Jump to search
Finite State Machine (FSM) is what we call it in our electronics course. I think FSM is a more commonly used term than FSA, at least in engeneering. For that reason, I made a page Finite state machine that redirects to here. --Aardwolf 14:39, 20 Oct 2005 (GMT)
- We used FSM in our Natural Language Processing course, but FSA in our Computation Theory course. Obviously different fields use different terminology. --Safalra 14:58, 20 Oct 2005 (GMT)
Two kinds of FSA language
It seems to me that languages classed as being in the FSA computational class actually fall into two categories:
- Those in which the language sets the limit.
- Those in which there's no language-imposed limit, but every program is forced to impose an upper bound on its number of states. Essentially, it would be a language capable of implementing arbitrarily large FSAs, but nothing more powerful.
Should these really be two separate computational classes? -- Smjg 14:08, 24 November 2007 (UTC)
- If it can implement no higher than an FSA, therefore can. solve only the problems an FSA can, is it. not just an FSA? a language where the limit is language set, it can only implement a subset of FSA's(since it is constant across programs). so they are different. --Yayimhere2(school) (talk) 18:58, 8 April 2026 (UTC)
- Im not sure whether these should be separate computational classes, but i think this is still an important distinction to be made, and there should be a name for these 2 categories. Infact, i had this exact thought of these 2 categories being separate and came to this talk page to talk about them, but here your message already lies.. Also, language-limited FSAs can be less useful than Combinational logic, yet still being able to do things which Combinational logic cannot do (such as looping forever). However, even limited FSAs can (but dont have to be) still be incredibly useful because maybe there is a limit of (3247863465783642678^^^^^^^^734893274263784)! states, which makes it a limited FSA, but with a limit youll likely never reach SB112 (talk) 17:22, 5 November 2026 (UTC)