it-swarm-vi.com

Ví dụ về máy nhà nước hữu hạn

Tôi đang tìm kiếm những ví dụ tốt về máy trạng thái hữu hạn; ngôn ngữ không đặc biệt quan trọng, chỉ là những ví dụ tốt.

Việc triển khai mã rất hữu ích (mã giả tổng quát), nhưng cũng rất hữu ích để thu thập các cách sử dụng khác nhau của FSM.

Các ví dụ không nhất thiết phải dựa trên máy tính, ví dụ ví dụ về mạng Đường sắt của Mike Dunlave, rất hữu ích.

26
ocodo

An toàn (kích hoạt sự kiện)

  • Trạng thái : Nhiều trạng thái "bị khóa", một trạng thái "đã mở khóa"
  • Chuyển tiếp : Các tổ hợp/phím chính xác chuyển bạn từ trạng thái bị khóa ban đầu sang trạng thái bị khóa gần hơn để mở khóa, cho đến khi bạn cuối cùng được mở khóa. Các kết hợp/khóa không chính xác đưa bạn trở lại trạng thái bị khóa ban đầu (đôi khi được gọi là không hoạt động .

Đèn giao thông (kích hoạt thời gian | cảm biến [sự kiện] được kích hoạt)

  • Hoa : ĐỎ, VÀNG, XANH (ví dụ đơn giản nhất)
  • Chuyển đổi : Sau khi bộ đếm thời gian thay đổi ĐỎ thành XANH, XANH thành VÀNG VÀ VÀNG sang ĐỎ. Cũng có thể được kích hoạt trên các xe cảm biến ở các trạng thái khác nhau (phức tạp hơn).

Máy bán hàng tự động (kích hoạt sự kiện, một biến thể của an toàn)

  • Các tiểu bang : IDLE, 5_CENT, 10_CENT, 15_CENT, 20_CENT, 25_CENT, v.v., VEND, THAY ĐỔI
  • Chuyển đổi : Trạng thái thay đổi khi chèn tiền xu, hóa đơn, chuyển đổi sang VEND theo số lượng mua chính xác (hoặc hơn), sau đó chuyển sang THAY ĐỔI hoặc IDLE (tùy thuộc Máy bán hàng tự động của bạn có đạo đức như thế nào)
28
aqua

Ví dụ về giao thức cổng biên

BGP là một giao thức hỗ trợ các quyết định định tuyến cốt lõi trên internet. Nó duy trì một bảng để xác định khả năng tiếp cận của máy chủ từ một nút nhất định và làm cho internet thực sự phi tập trung.

Trong mạng, mỗi nút BGP là một máy ngang hàng và sử dụng máy trạng thái hữu hạn, với một trong sáu trạng thái Idle , Kết nối, Hoạt động, OpenSent, OpenConfirm, và Thành lập. Mỗi kết nối ngang hàng trong mạng duy trì một trong những trạng thái này.

Giao thức BGP xác định các thông điệp được gửi đến các đồng nghiệp để thay đổi trạng thái của chúng.

Bech statechart.

BGP statechart

Nhàn rỗi

Trạng thái đầu tiên Không hoạt động . Ở trạng thái này, BGP khởi tạo tài nguyên và từ chối các nỗ lực kết nối trong nước và bắt đầu kết nối với thiết bị ngang hàng.

Kết nối

Trạng thái thứ hai Kết nối . Ở trạng thái này, bộ định tuyến chờ kết nối hoàn tất và chuyển sang trạng thái OpenSent nếu thành công. Nếu không thành công, nó sẽ đặt lại bộ hẹn giờ ConnectR tem và chuyển sang trạng thái Hoạt động khi hết hạn.

Hoạt động

Ở trạng thái Hoạt động , bộ định tuyến đặt lại bộ hẹn giờ ConnectR tem về 0 và trở về Kết nối trạng thái.

OpenSent

Ở trạng thái OpenSent , bộ định tuyến sẽ gửi một thông báo Mở và chờ trả lại. Các thông điệp lưu giữ được trao đổi và sau khi nhận thành công, bộ định tuyến được đặt ở trạng thái Được thiết lập .

Thành lập

Ở trạng thái Được thiết lập , bộ định tuyến có thể gửi/nhận: Keepalive; Cập nhật; và thông báo tin nhắn đến/từ ngang hàng của nó.

Khác thông tin về BGP có trên wikipedia

14
ocodo

Chúng hữu ích cho việc mô hình hóa tất cả các loại. Ví dụ: một chu kỳ bầu cử có thể được mô hình hóa với các quốc gia dọc theo dòng (chính phủ bình thường) - cuộc gọi được gọi là -> (chiến dịch sớm) --Parliament đã giải thể -> (chiến dịch nặng nề) - bầu cử -> (kiểm phiếu ). Sau đó, (kiểm phiếu) - không chiếm đa số -> (đàm phán liên minh) - đạt được sự đồng thuận -> (chính phủ bình thường) hoặc (kiểm phiếu) - đa số -> (chính phủ bình thường). Tôi đã thực hiện một biến thể trên sơ đồ này trong một trò chơi với một phụ bản chính trị.

Chúng cũng được sử dụng trong các khía cạnh khác của trò chơi: AI thường dựa trên trạng thái; chuyển tiếp giữa các menu và cấp độ, và chuyển tiếp khi chết hoặc mức độ hoàn thành thường được mô hình hóa tốt bởi các FSM.

7
Peter Taylor

Trình phân tích cú pháp CSV được sử dụng trong jquery-csv trình cắm

Đó là một Chomsky cơ bản Ngữ pháp loại III trình phân tích cú pháp.

Mã thông báo regex được sử dụng để đánh giá dữ liệu trên cơ sở char-by-char. Khi gặp char điều khiển, mã được chuyển đến câu lệnh chuyển đổi để đánh giá thêm dựa trên trạng thái bắt đầu. Các ký tự không điều khiển được nhóm và sao chép en masse để giảm số lượng thao tác sao chép chuỗi cần thiết.

Mã thông báo:

var tokenizer = /("|,|\n|\r|[^",\r\n]+)/;

Nhóm khớp đầu tiên là các ký tự điều khiển: dấu phân cách giá trị (") dấu phân cách giá trị (,) và dấu tách mục nhập (tất cả các biến thể của dòng mới). Trận đấu cuối xử lý nhóm char không kiểm soát.

Có 10 quy tắc mà trình phân tích cú pháp phải đáp ứng:

  • Quy tắc số 1 - Một mục nhập trên mỗi dòng, mỗi dòng kết thúc bằng một dòng mới
  • Quy tắc số 2 - Trailing dòng mới ở cuối tập tin bị bỏ qua
  • Quy tắc số 3 - Hàng đầu tiên chứa dữ liệu tiêu đề
  • Quy tắc số 4 - Không gian được coi là dữ liệu và các mục nhập không được chứa dấu phẩy
  • Quy tắc số 5 - Các dòng có thể hoặc không được phân cách bằng dấu ngoặc kép
  • Quy tắc số 6 - Các trường chứa dấu ngắt dòng, dấu ngoặc kép và dấu phẩy phải được đặt trong dấu ngoặc kép
  • Quy tắc số 7 - Nếu trích dẫn kép được sử dụng để bao quanh các trường, thì một trích dẫn kép xuất hiện bên trong một trường phải được thoát bằng cách đặt trước nó bằng một trích dẫn kép khác
  • Sửa đổi số 1 - Một trường không trích dẫn có thể hoặc có thể
  • Sửa đổi số 2 - Một trường được trích dẫn có thể có hoặc không
  • Sửa đổi số 3 - Trường cuối cùng trong mục nhập có thể có hoặc không chứa giá trị null

Lưu ý: 7 quy tắc hàng đầu được lấy trực tiếp từ IETF RFC 418 . 3 cái cuối cùng đã được thêm vào để bao gồm các trường hợp Edge được giới thiệu bởi các ứng dụng bảng tính hiện đại (ví dụ Excel, Bảng tính Google) không phân định (ví dụ như trích dẫn) tất cả các giá trị theo mặc định. Tôi đã cố gắng đóng góp lại các thay đổi cho RFC nhưng vẫn chưa nghe thấy phản hồi cho yêu cầu của tôi.

Đủ thông tin, đây là sơ đồ:

CSV parser finite state machine

Hoa Kỳ:

  1. trạng thái ban đầu cho một mục và/hoặc một giá trị
  2. một trích dẫn đã được bắt gặp
  3. một trích dẫn thứ hai đã được bắt gặp
  4. một giá trị chưa được trích dẫn đã gặp phải

Chuyển đổi:

  • a. kiểm tra cả giá trị được trích dẫn (1), giá trị không trích dẫn (3), giá trị null (0), mục nhập null (0) và mục nhập mới (0)
  • b. kiểm tra một trích dẫn thứ hai char (2)
  • c. kiểm tra báo giá đã thoát (1), kết thúc giá trị (0) và kết thúc mục nhập (0)
  • d. kiểm tra kết thúc giá trị (0) và kết thúc mục nhập (0)

Lưu ý: Nó thực sự thiếu một trạng thái. Cần có một dòng từ 'c' -> 'b' được đánh dấu bằng trạng thái '1' vì một dấu phân cách thứ hai đã thoát có nghĩa là dấu phân cách thứ nhất vẫn đang mở. Trong thực tế, có lẽ sẽ tốt hơn nếu đại diện cho nó như là một quá trình chuyển đổi khác. Tạo ra chúng là một nghệ thuật, không có cách chính xác duy nhất.

Lưu ý: Nó cũng thiếu trạng thái thoát nhưng trên dữ liệu hợp lệ, trình phân tích cú pháp luôn kết thúc khi chuyển đổi 'a' và không có trạng thái nào khả thi vì không còn gì để phân tích.

Sự khác biệt giữa các quốc gia và chuyển tiếp:

Một trạng thái là hữu hạn, có nghĩa là nó chỉ có thể được suy ra có nghĩa là một điều.

Một chuyển đổi đại diện cho dòng chảy giữa các trạng thái để nó có thể có nghĩa là nhiều thứ.

Về cơ bản, mối quan hệ chuyển đổi trạng thái-> là 1 -> * (tức là một-nhiều). Trạng thái xác định 'nó là gì' và quá trình chuyển đổi xác định 'cách xử lý'.

Lưu ý: Đừng lo lắng nếu ứng dụng trạng thái/chuyển tiếp không cảm thấy trực quan, nó không trực quan. Phải mất một số tương ứng với ai đó thông minh hơn tôi nhiều trước khi cuối cùng tôi có ý tưởng để gắn bó.

Mã giả:

csv = // csv input string

// init all state & data
state = 0
value = ""
entry = []
output = []

endOfValue() {
  entry.Push(value)
  value = ""
}

endOfEntry() {
  endOfValue()
  output.Push(entry)
  entry = []
}

tokenizer = /("|,|\n|\r|[^",\r\n]+)/gm

// using the match extension of string.replace. string.exec can also be used in a similar manner
csv.replace(tokenizer, function (match) {
  switch(state) {
    case 0:
      if(opening delimiter)
        state = 1
        break
      if(new-line)
        endOfEntry()
        state = 0
        break
      if(un-delimited data)
        value += match
        state = 3
        break
    case 1:
      if(second delimiter encountered)
        state = 2
        break
      if(non-control char data)
        value += match
        state = 1
        break
    case 2:
      if(escaped delimiter)
        state = 1
        break
      if(separator)
        endOfValue()
        state = 0
        break
      if(newline)
        endOfEntry()
        state = 0
        break
    case 3:
      if(separator)
        endOfValue()
        state = 0
        break
      if(newline)
        endOfEntry()
        state = 0
        break
  }
}

Lưu ý: Đây là Gist, trong thực tế có rất nhiều điều cần xem xét. Ví dụ: kiểm tra lỗi, giá trị null, một dòng trống ở cuối (nghĩa là hợp lệ), v.v.

Trong trường hợp này, trạng thái là điều kiện của mọi thứ khi khối kết hợp biểu thức chính quy kết thúc một lần lặp. Việc chuyển đổi được thể hiện dưới dạng các báo cáo trường hợp.

Là con người, chúng ta có xu hướng đơn giản hóa các hoạt động cấp thấp thành các tóm tắt cấp cao hơn nhưng làm việc với một FSM hoạt động với các hoạt động cấp thấp. Mặc dù các trạng thái và chuyển tiếp rất dễ dàng để làm việc với từng cá nhân, nhưng về cơ bản, rất khó để hình dung toàn bộ tất cả cùng một lúc. Tôi thấy dễ dàng nhất để đi theo từng con đường thực hiện lặp đi lặp lại cho đến khi tôi có thể hiểu được cách thức chuyển đổi diễn ra. Đó là vua thích học toán cơ bản, bạn sẽ không có khả năng đánh giá mã từ cấp cao hơn cho đến khi các chi tiết cấp thấp bắt đầu tự động.

Ngoài ra: Nếu bạn nhìn vào việc thực hiện thực tế, có rất nhiều chi tiết bị thiếu. Đầu tiên, tất cả các con đường không thể sẽ ném ngoại lệ cụ thể. Không thể đánh chúng nhưng nếu bất cứ điều gì phá vỡ chúng sẽ hoàn toàn kích hoạt ngoại lệ trong người chạy thử. Thứ hai, các quy tắc của trình phân tích cú pháp cho những gì được phép trong chuỗi dữ liệu CSV 'hợp pháp' khá lỏng lẻo nên mã cần thiết để xử lý nhiều trường hợp Edge cụ thể. Bất kể thực tế đó, đây là quá trình được sử dụng để chế nhạo FSM trước tất cả các sửa lỗi, tiện ích mở rộng và tinh chỉnh.

Như với hầu hết các thiết kế, nó không phải là một đại diện chính xác của việc thực hiện nhưng nó phác thảo các phần quan trọng. Trong thực tế, thực tế có 3 hàm phân tích cú pháp khác nhau xuất phát từ thiết kế này: trình phân tách dòng cụ thể csv, trình phân tích cú pháp một dòng và trình phân tích cú pháp nhiều dòng hoàn chỉnh. Tất cả đều hoạt động theo cách tương tự, chúng khác nhau ở cách chúng xử lý ký tự dòng mới.

4
Evan Plaice

Tôi đã thấy rằng suy nghĩ về/mô hình thang máy (thang máy) là một ví dụ tốt về một máy trạng thái hữu hạn. Nó đòi hỏi ít trong cách giới thiệu, nhưng cung cấp một tình huống tầm thường để thực hiện.

Các tiểu bang, ví dụ, ở tầng trệt, ở tầng một, v.v., và di chuyển từ tầng một xuống tầng ba, hoặc di chuyển từ tầng ba xuống tầng trệt, nhưng hiện tại giữa tầng 3 và 2, v.v.

Hiệu ứng của các nút trong lồng nâng và tại các tầng tự cung cấp đầu vào, hiệu ứng phụ thuộc vào cả hai nút được nhấn cùng với trạng thái hiện tại.

Mỗi tầng, ngoại trừ trên cùng và dưới cùng, sẽ có hai nút: một để yêu cầu thang máy đi lên, tầng còn lại để đi xuống.

3
jan

FSM đơn giản trong Java

int i=0;

while (i<5) {
 switch(i) {
   case 0:
     System.out.println("State 0");
     i=1;
     break;
   case 1:
     System.out.println("State 1");
     i=6;
     break;
   default:
     System.out.println("Error - should not get here");
     break;      
  }

} 

Có bạn đi. OK, nó không xuất sắc, nhưng nó cho thấy ý tưởng.

Bạn sẽ thường tìm thấy các FSM trong các sản phẩm viễn thông vì họ cung cấp một giải pháp đơn giản cho một tình huống phức tạp khác.

3
Gary Rowe

OK, đây là một ví dụ. Giả sử bạn muốn phân tích một số nguyên. Nó sẽ đi một cái gì đó như dd* trong đó d là một chữ số nguyên.

state0:
    if (!isdigit(*p)) goto error;
    p++;
    goto state1;
state1:
    if (!isdigit(*p)) goto success;
    p++;
    goto state1;

Tất nhiên, như @Gary đã nói, bạn có thể ngụy trang những gotos đó bằng một câu lệnh chuyển đổi và biến trạng thái. Lưu ý rằng có thể được cấu trúc theo mã này, đó là đẳng cấu với biểu thức chính quy ban đầu:

if (isdigit(*p)){
    p++;
    while(isdigit(*p)){
        p++;
    }
    // success
}
else {
    // error
}

Tất nhiên bạn cũng có thể làm điều đó với một bảng tra cứu.

Máy trạng thái hữu hạn có thể được thực hiện theo nhiều cách, và nhiều thứ có thể được mô tả như là trường hợp của máy trạng thái hữu hạn. Nó không phải là một "thứ" nhiều như một khái niệm, để suy nghĩ về mọi thứ.

Ví dụ về mạng lưới đường sắt

Một ví dụ về FSM là mạng lưới đường sắt.

Có một số lượng hữu hạn các công tắc trong đó một chuyến tàu có thể đi vào một trong hai đường ray.

Có một số lượng hữu hạn các bản nhạc kết nối các công tắc này.

Bất cứ lúc nào, một chuyến tàu đang ở trên một tuyến đường, nó có thể được gửi đến một tuyến đường khác bằng cách vượt qua một công tắc, dựa trên một chút thông tin đầu vào.

2
Mike Dunlavey

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

module Dec_Acts
 def do_next
    @now = @next
    case @now
    when :invite
      choose_round_partner
      @next = :wait
    when :listen
      @next = :respond
    when :respond
      evaluate_invites
      @next = :update_in
    when :wait
      @next = :update_out
    when :update_in, :update_out
      update_edges
      clear_invites
      @next = :exchange
    when :exchange
      update_colors
      clear_invites
      @next = :choose
    when :choose
      reset_variables
      choose_role
    when :done
      @next = :done
    end
  end
end

Đó là hành vi của một nút tính toán đơn trong một hệ thống phân tán, thiết lập sơ đồ truyền thông dựa trên liên kết. Nhiều hơn hoặc ít hơn. Ở dạng Đồ họa, nó trông giống như thế này:

enter image description here

2
philosodad

Kiểm tra liên kết này để biết một số ví dụ đơn giản về phân tích từ vựng (FSM):

http://ironbark.bendigo.latcoat.edu.au/subjects/SS/clect/clect03.html

Bạn cũng có thể xem "cuốn sách rồng" để biết ví dụ (không phải là đọc nhẹ)

http://en.wikipedia.org/wiki/Compilers:_Principles,_T kỹ thuật,_and_Tools

1
jmq

Trong thực tế, Máy trạng thái thường được sử dụng cho:

  • Mục đích thiết kế (mô hình hóa các hành động khác nhau trong một chương trình)
  • Trình phân tích cú pháp ngôn ngữ tự nhiên (ngữ pháp)
  • Phân tích cú pháp chuỗi

Một ví dụ sẽ là Máy trạng thái quét một chuỗi để xem nó có đúng cú pháp không. Ví dụ, mã Zip Hà Lan được định dạng là "1234 AB". Phần đầu tiên chỉ có thể chứa số, chữ cái thứ hai. Một Máy trạng thái có thể được viết để theo dõi xem nó có ở trạng thái SỐ hay ở trạng thái LETTER hay không và nếu gặp phải đầu vào sai, hãy từ chối nó.

Máy trạng thái chấp nhận này có hai trạng thái: số và alpha. Máy trạng thái bắt đầu ở trạng thái số và bắt đầu đọc các ký tự của chuỗi để kiểm tra. Nếu gặp phải các ký tự không hợp lệ trong bất kỳ trạng thái nào, hàm sẽ trả về giá trị Sai, từ chối đầu vào là không hợp lệ.

Mã Python:

import string

STATE_NUMERIC = 1
STATE_ALPHA = 2

CHAR_SPACE = " "

def validate_zipcode(s):
cur_state = STATE_NUMERIC

for char in s:
    if cur_state == STATE_NUMERIC:
        if char == CHAR_SPACE:
            cur_state = STATE_ALPHA
        Elif char not in string.digits:
            return False
    Elif cur_state == STATE_ALPHA:
        if char not in string.letters:
            return False
return True

zipcodes = [
    "3900 AB",
    "45D6 9A",
]

for zipcode in zipcodes:
    print zipcode, validate_zipcode(zipcode)

Nguồn: (hữu hạn-) Máy trạng thái trong thực tế

0
theD