Máy trạng thái hữu hạn

Máy trạng thái hữu hạn (finite-state machine FSM) hoặc Máy tự động trạng thái hữu hạn (finite-state automaton FSA), hoặc là máy tự động hữu hạn, hoặc gọi đơn giản là máy trạng thái, là một mô hình tính toán toán học. Nó là một máy trừu tượng luôn có trạng thái nằm trong tổng hữu hạn các trạng thái tại bất kỳ thời điểm nào. Máy trạng thái hữu hạn có thể chuyển từ trạng thái này sang trạng thái khác để phù hợp với đầu vào; sự thay đổi này được gọi là quá trình chuyển đổi. Máy trạng thái hữu hạn được xác định bởi danh sách các trạng thái của nó, trạng thái khởi đầu, và các điều kiện cho từng sự chuyển đổi trạng thái.

Hành vi của máy trạng thái có thể được quan sát qua nhiều thiết bị hiện đại, đó là việc thực hiện một chuỗi các hành động định trước tùy vào chuỗi sự kiện mà chúng được lập trình.

Máy trạng thái hữu hạn có công suất tính toán thấp hơn một số mô hình tính toán khác như máy Turing.^[1] Sự khác biệt năng lực tính toán cũng có nghĩa là có những bài toán mà máy Turing có thể thực hiện, nhưng máy trạng thái thì không. Nguyên nhân là do bộ nhớ của máy trạng thái bị giới hạn bởi số trạng thái. Máy trạng thái được nghiên cứu trong lĩnh vực tổng quát hơn thuộc lý thuyết tự động.

Ví dụ: Của quay hoạt động bằng tiền xu

Khái niệm và thuật ngữ

Cách mô tả

Bảng trạng thái/sự kiện

Máy trạng thái UML

Máy trạng thái SDL

Các dạng biểu đồ trạng thái khác

Ứng dụng

Phân loại

Theo bộ chấp nhận và nhận dạng

Bộ phân loại

Bộ chuyển dịch

Bộ phát sinh

Bộ xác định

Ý nghĩa tương tự

Mô hình toán học

Tối ưu hóa

Cài đặt

Ứng dụng phần cứng

Ứng dụng phần mềm

Máy và trình biên dịch trạng thái hữu hạn

Xem thêm

• Abstract state machines (ASM)
• Artificial intelligence (AI)
• Abstract State Machine Language (AsmL)
• Behavior model
• Communicating finite-state machine
• Control system
• Control table
• Decision tables
• DEVS: Discrete Event System Specification
• Extended finite-state machine (EFSM)
• Finite state machine with datapath
• Hidden Markov model
• Petri net
• Pushdown automaton
• Quantum finite automata (QFA)
• Recognizable language
• Sequential logic
• Specification and Description Language
• State diagram
• State pattern
• SCXML
• Transition system
• Tree automaton
• Turing machine
• UML state machine
• YAKINDU Statechart Tools

Tham khảo

1. . ISBN 0-8247-2275-2 https://books.google.com/books?id=W2YLBIdeLIEC&printsec=frontcover&f=false. {{Chú thích sách}}: |title= trống hay bị thiếu (trợ giúp)|tựa đề= trống hay bị thiếu (trợ giúp)

Đọc thêm

Chung

• . ISBN 978-0-521-84425-3. {{Chú thích sách}}: |title= trống hay bị thiếu (trợ giúp)|tựa đề= trống hay bị thiếu (trợ giúp)
• Wagner, F., "Modeling Software with Finite State Machines: A Practical Approach", Auerbach Publications, 2006, ISBN 0-8493-8086-3.
• ITU-T, Recommendation Z.100 Specification and Description Language (SDL)
• Samek, M., Practical Statecharts in C/C++, CMP Books, 2002, ISBN 1-57820-110-1.
• Samek, M., Practical UML Statecharts in C/C++, 2nd Edition, Newnes, 2008, ISBN 0-7506-8706-1.
• Gardner, T., Advanced State Management Lưu trữ ngày 19 tháng 11 năm 2008 tại Wayback Machine, 2007
• Cassandras, C., Lafortune, S., "Introduction to Discrete Event Systems". Kluwer, 1999, ISBN 0-7923-8609-4.
• Timothy Kam, Synthesis of Finite State Machines: Functional Optimization. Kluwer Academic Publishers, Boston 1997, ISBN 0-7923-9842-4
• Tiziano Villa, Synthesis of Finite State Machines: Logic Optimization. Kluwer Academic Publishers, Boston 1997, ISBN 0-7923-9892-0
• Carroll, J., Long, D., Theory of Finite Automata with an Introduction to Formal Languages. Prentice Hall, Englewood Cliffs, 1989.
• Kohavi, Z., Switching and Finite Automata Theory. McGraw-Hill, 1978.
• Gill, A., Introduction to the Theory of Finite-state Machines. McGraw-Hill, 1962.
• Ginsburg, S., An Introduction to Mathematical Machine Theory. Addison-Wesley, 1962.

Máy trạng thái hữu hạn trong Lý thuyết khoa học máy tính

• . ISBN 0-13-913368-2. {{Chú thích sách}}: |title= trống hay bị thiếu (trợ giúp)|tựa đề= trống hay bị thiếu (trợ giúp)
• . ISBN 0-7216-1768-9. {{Chú thích sách}}: |title= trống hay bị thiếu (trợ giúp)|tựa đề= trống hay bị thiếu (trợ giúp)
• . Library of Congress Card Catalog Number 67-25924. {{Chú thích sách}}: |title= trống hay bị thiếu (trợ giúp)|tựa đề= trống hay bị thiếu (trợ giúp)
• . ISBN 0-521-20402-X. {{Chú thích sách}}: |title= trống hay bị thiếu (trợ giúp)|tựa đề= trống hay bị thiếu (trợ giúp)
• . ISBN 0-8053-0143-7. {{Chú thích sách}}: |title= trống hay bị thiếu (trợ giúp)|tựa đề= trống hay bị thiếu (trợ giúp)
• . ISBN 0-12-206382-1. {{Chú thích sách}}: |title= trống hay bị thiếu (trợ giúp)|tựa đề= trống hay bị thiếu (trợ giúp)
• . ISBN 0-201-02988-X. {{Chú thích sách}}: |title= trống hay bị thiếu (trợ giúp)|tựa đề= trống hay bị thiếu (trợ giúp)
• . ISBN 0-201-44124-1. {{Chú thích sách}}: |title= trống hay bị thiếu (trợ giúp)|tựa đề= trống hay bị thiếu (trợ giúp)
• . ISBN 0-444-00249-9. {{Chú thích sách}}: |title= trống hay bị thiếu (trợ giúp)|tựa đề= trống hay bị thiếu (trợ giúp)
• . ISBN 0-387-94907-0. {{Chú thích sách}}: |title= trống hay bị thiếu (trợ giúp)|tựa đề= trống hay bị thiếu (trợ giúp)
• . ISBN 0-13-262478-8. {{Chú thích sách}}: |title= trống hay bị thiếu (trợ giúp)|tựa đề= trống hay bị thiếu (trợ giúp)
• . ISBN 978-0-7637-3798-6. {{Chú thích sách}}: |title= trống hay bị thiếu (trợ giúp)|tựa đề= trống hay bị thiếu (trợ giúp)
• . ISBN 0-201-53082-1. {{Chú thích sách}}: |title= trống hay bị thiếu (trợ giúp)|tựa đề= trống hay bị thiếu (trợ giúp)
• . ISBN 0-521-55380-6. {{Chú thích sách}}: |title= trống hay bị thiếu (trợ giúp)|tựa đề= trống hay bị thiếu (trợ giúp)
• . ISBN 0-7637-3834-4. {{Chú thích sách}}: |title= trống hay bị thiếu (trợ giúp)|tựa đề= trống hay bị thiếu (trợ giúp)
• . ISBN 0-534-95097-3. {{Chú thích sách}}: |title= trống hay bị thiếu (trợ giúp)|tựa đề= trống hay bị thiếu (trợ giúp)
• . ISBN 0-06-047208-1. {{Chú thích sách}}: |title= trống hay bị thiếu (trợ giúp)|tựa đề= trống hay bị thiếu (trợ giúp)

Máy trạng thái trừu tượng trong lý thuyết khoa học máy tính

• . doi:10.1145/343369.343384. {{Chú thích tạp chí}}: ; |title= trống hay bị thiếu (trợ giúp)|tựa đề= trống hay bị thiếu (trợ giúp)

Học máy dựa trên thuật toán trạng thái hữu hạn

• . ISBN 0-07-042807-7. {{Chú thích sách}}: |title= trống hay bị thiếu (trợ giúp)|tựa đề= trống hay bị thiếu (trợ giúp)

Kỹ thuật phần cứng: tối thiểu trạng thái và sự tổ hợp mạch tuần tự

• . Library of Congress Card Catalog Number 67-25924. {{Chú thích sách}}: |title= trống hay bị thiếu (trợ giúp)|tựa đề= trống hay bị thiếu (trợ giúp)
• . ISBN 0-471-08840-4. {{Chú thích sách}}: |title= trống hay bị thiếu (trợ giúp)|tựa đề= trống hay bị thiếu (trợ giúp)
• . Library of Congress Card Catalog Number 65-17394. {{Chú thích sách}}: |title= trống hay bị thiếu (trợ giúp)|tựa đề= trống hay bị thiếu (trợ giúp)
• . Library of Congress Card Catalog Number 65-17394. {{Chú thích sách}}: |title= trống hay bị thiếu (trợ giúp)|tựa đề= trống hay bị thiếu (trợ giúp)

Chuỗi quá trình Markov hữu hạn

"We may think of a Markov chain as a process that moves successively through a set of states s₁, s₂, …, s_r. … if it is in state s_i it moves on to the next stop to state s_j with probability p_ij. These probabilities can be exhibited in the form of a transition matrix" (Kemeny (1959), p. 384)

Finite Markov-chain processes are also known as subshifts of finite type.

• . Library of Congress Card Catalog Number 67-25924. {{Chú thích sách}}: |title= trống hay bị thiếu (trợ giúp)|tựa đề= trống hay bị thiếu (trợ giúp)
• . Library of Congress Card Catalog Number 59-12841. {{Chú thích sách}}: |title= trống hay bị thiếu (trợ giúp)|tựa đề= trống hay bị thiếu (trợ giúp)

Chapter 6 "Finite Markov Chains".

Liên kết ngoài

• Finite State Automata trên DMOZ
• Modeling a Simple AI behavior using a Finite State Machine Example of usage in Video Games
• Free On-Line Dictionary of Computing description of Finite State Machines
• NIST Dictionary of Algorithms and Data Structures description of Finite State Machines
• Interactive FSM: Control Circuit Lưu trữ ngày 24 tháng 3 năm 2016 tại Wayback Machine, demonstrates the logic flow of the Finite State Machines.
• FSM simulator, simulates DFAs, NFAs and ε-NFAs, including generated by regular expression.
• A brief overview of state machine types, comparing theoretical aspects of Mealy, Moore, Harel & UML state machines.
• Turing Machine and FSM simulator Lưu trữ ngày 10 tháng 2 năm 2018 tại Wayback Machine Tuple-based FSM and Turing Machine simulator with simulation of tape.