MÁY KẾT CẤU NHÀ NƯỚC LÀ GÌ?

Máy trạng thái hữu hạn được sử dụng để chuyển trạng thái giữa các trạng thái bên trong thông qua các sự kiện đầu vào. Sức mạnh của FSM đến từ khả năng xác định rõ ràng các hành vi khác nhau trong các điều kiện khác nhau. Thông thường, FSM được sử dụng trong các kịch bản lặp lại liên tục, đánh giá trạng thái hiện tại của trạng thái khi gặp sự kiện hoặc đầu vào.

Bạn thử xem: Máy tate thành phẩm là gì?

Để bạn dễ hình dung hơn về cách áp dụng máy trạng thái, tôi sẽ đưa ra một ví dụ đơn giản về máy pha cà phê:

*

Hình 1: Máy pha cà phê

Máy pha cà phê trên có 3 trạng thái: “nhàn rỗi”, “miếng trơ”, “lựa chọn tùy chọn”, 3 sự kiện là “insert_corner”, “chọn tùy chọn”, “coffee_dispensed”

Đầu tiên là máy pha cà phê “nhàn rỗi”sau khi gặp phải sự kiện “insert_corner”nó chuyển sang trạng thái “miếng trơ”sau đó gặp gỡ sự kiện “chọn tùy chọn” nó thay đổi trạng thái “lựa chọn tùy chọn”. Trong điều kiện “lựa chọn tùy chọn” Đây là một sự kiện “coffee_dispensed” sau đó nó đi đến trạng thái “nhàn rỗi”.

Các ví dụ khác về thang máy:

*

*

Hình 2: Máy trạng thái cho thang máy

Trong ví dụ này, chúng ta có 2 trạng thái “Đất” một “Ngày thứ nhất”. 2 sự kiện đầu tiên là “Ở trên cùng”, “Chủ đề”. Giả sử rằng ở trạng thái “Đất” Cô ấy đã gặp một sự kiện “Ở trên cùng” thì thang máy sẽ đi vào trạng thái “Ngày thứ nhất”và nếu có một sự kiện “Chủ đề” sau đó thang máy vẫn hoạt động bình thường “Đất”. Khi ở trạng thái “Ngày thứ nhất” nếu bạn có một sự kiện “Ở trên cùng” sau đó thang máy vẫn hoạt động bình thường “Ngày thứ nhất”và nếu có một sự kiện “Chủ đề” sau đó nó sẽ đi đến trạng thái “Đất”.

Đây chỉ là 2 ví dụ đơn giản để chúng ta hình dung máy trạng thái là gì.

Xem thêm: Mesenteric là gì – Nghĩa của từ mesenteric

2. Định nghĩa

Máy trạng thái, là một mô hình toán học. Nó là một cỗ máy trừu tượng mà trạng thái của nó là một tổng hữu hạn các trạng thái, tại một thời điểm nhất định. Một 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 để thích ứng với đầu vào biến này được gọi là máy chuyển trạng thái. Máy trạng thái được xác định bởi danh sách các trạng thái của nó, trạng thái ban đầu và điều kiện cho mỗi chuyển đổi trạng thái.

*

*

Hình 3: Phân loại máy trạng thái

Nhìn vào hình trên, chúng ta có thể thấy rằng máy trạng thái có thể được chia thành 2 loại.

1. Máy trạng thái với đầu ra

2. Máy trạng thái không có đầu ra (hôm nay mình sẽ bàn về vấn đề này)

Đối với FA (Tự động hóa hữu hạn) không có đầu ra, chúng ta có thể chia nó thành Máy hữu hạn xác định (DFA), Máy hữu hạn không xác định (NFA)

2.1 DFA

Một DFA có thể được biểu diễn bằng một tập hợp (Q, ∑, δ, q0, F)

Trong đó:

Q: là tập hữu hạn các trạng thái∑: là tập các ký tự đầu vào ᴠ: hàm chuyển trạng thái Q × ∑ → Qq0: là trạng thái đầu (q0 ∈ Q) .F: là tập các trạng thái kết thúc (F ⊆ Q)

Một ví dụ đơn giản cho DFA.

Q = {a, b, c} ∑ = {0, 1}, q0 = {a} F = {c}

Hàm chuyển đổi trạng thái được đưa ra trong bảng dưới đây:

+ ————- + — + — + | Trạng thái / Mục nhập | 0 | 1 | + ————- + — + — + | a | a | b || b | c | một || c | b | c | + ———— + — + — +
Hình 4: Biểu diễn đồ họa cho ví dụ được chấp nhận DFAA: 10

FA đầu tiên đang ở trong tình trạng tốt “một”sau đó khi đầu vào là “Đầu tiên” sau đó thay đổi trạng thái “b”trong điều kiện “b”nếu gặp “0” sau đó thay đổi trạng thái “vs”

—> được chấp nhận

Một số ví dụ được chấp nhận khác là: 010,11101,…

Một số ví dụ bị từ chối là: 100

FA đang ở trạng thái “một”trong suốt cuộc họp “Đầu tiên” sau đó thay đổi trạng thái “b”trong điều kiện “b” gặp gỡ “0” đổi “vs”tiếp tục gặp 0, FA hiện tại “b”.

—> bị từ chối

Một số ví dụ bị từ chối khác là: 0,1,11,1001,…

2.2 ENF

Một NFA có thể được biểu diễn bằng một tập hợp (Q, ∑, δ, q0, F)

Trong đó:

Q: là tập hữu hạn các trạng thái∑: là tập các ký tự đầu vàoδ: hàm chuyển trạng thái Q × ∑ → 2 ^ Q (Vì NFA có thể chuyển sang nhiều trạng thái khi đang ở một trạng thái). trạng thái ban đầu (q0 ∈ Q) .F: là tập hợp các trạng thái đầu cuối (F ⊆ Q)

Chủ đề NFA mẫu

Q = {a, b, c} ∑ = {0, 1} q0 = {a} F = {c}

Hàm chuyển đổi trạng thái được đưa ra trong bảng dưới đây:

+ ————- + —– + —– + | Trạng thái / Mục nhập | 0 | 1 | + ———— + —– + —– + | a | a, b | b || b | c | a, c || c | b, c | c | + ——– + —– + —– +

TH1: khi ở trạng thái “một”tiếp tục gặp “0”máy trạng thái sẽ thay đổi thành “một”, “b”

TH2: khi ở trạng thái “b”gặp gỡ “0” máy trạng thái sẽ chuyển sang trạng thái “vs” (trạng thái cuối cùng)

Một số ví dụ bị từ chối là: Vì máy trạng thái chấp nhận tất cả các chuỗi có độ dài lớn hơn 2, chúng tôi chỉ có 2 chuỗi bị từ chối: 0, 1

Cần lưu ý

Trong DFA:

Chỉ có thể chuyển sang trạng thái tiếp theo Không có lựa chọn hoặc chuyển động ngẫu nhiên

Trong ANF:

Có thể chuyển đổi sang nhiều trạng thái tiếp theo Trạng thái tiếp theo có thể được chọn ngẫu nhiên hoặc tất cả các trạng thái có thể được thực hiện đồng thời

3. Ví dụ đơn giản với Pathon

  • Tôi có thể học sáng tác nhạc ở đâu?
  • Bạn bán gỗ bỏ hoang ở đâu?
  • Làm thế nào để vượt qua shell để fc?
  • Cài đặt windows ở đâu?