Tự động hóa hữu hạn được thực hiện như thế nào trong mã?

Question

Làm cách nào để triển khai dfa hoặc nfa cho vấn đề đó trong mã Python?

Một số cách hay để làm điều đó trong python là gì? Và chúng có từng được sử dụng trong các dự án thế giới thực không?

Answer 1

Cách đơn giản để thể hiện DFA là từ điển từ điển. Đối với mỗi tiểu bang, hãy tạo một từ điển được khóa bằng các chữ cái của bảng chữ cái và sau đó là một từ điển toàn cầu được khóa bởi các trạng thái. Ví dụ, DFA sau từ Wikipedia article on DFAs

có thể được đại diện bởi một từ điển như thế này:

dfa = {0:{'0':0, '1':1}, 
     1:{'0':2, '1':0}, 
     2:{'0':1, '1':2}} 

Để "chạy" một DFA chống lại một chuỗi đầu vào rút ra từ bảng chữ cái trong câu hỏi (sau khi chỉ định trạng thái ban đầu và tập hợp các giá trị chấp nhận) rất đơn giản:

def accepts(transitions,initial,accepting,s): 
    state = initial 
    for c in s: 
     state = transitions[state][c] 
    return state in accepting 

Bạn bắt đầu trong trạng thái ban đầu, bước qua ký tự chuỗi theo ký tự và mỗi bước chỉ cần tìm kiếm trạng thái tiếp theo. Khi bạn hoàn thành bước qua chuỗi, bạn chỉ cần kiểm tra xem trạng thái cuối cùng có nằm trong tập hợp các trạng thái chấp nhận hay không.

Ví dụ

>>> accepts(dfa,0,{0},'1011101') 
True 
>>> accepts(dfa,0,{0},'10111011') 
False 

Đối NFAs bạn có thể lưu trữ bộ trạng thái có thể chứ không phải từng tiểu bang trong từ điển chuyển và sử dụng các mô-đun random để chọn trạng thái tiếp theo từ tập các trạng thái có thể.

Answer 2

tốt, ở đây tôi trình bày một giải pháp đệ quy cho NFA.

xem xét NFA sau:

quá trình chuyển đổi có thể được biểu diễn bằng danh sách liệt kê như sau:

chuyển = [[[0,1],[0]], [[4],[2]], [[4],[3]], [[4],[4]],[[4],[4]]]

Lưu ý: Nhà nước 4 là một giả thuyết tiểu bang. Một khi bạn đi đến trạng thái đó, bạn không thể di chuyển xa hơn. Nó rất hữu ích khi bạn không thể đọc đầu vào từ trạng thái hiện tại. Bạn trực tiếp đến tiểu bang 4 và nói rằng đầu vào không được chấp nhận cho tiến trình hiện tại (Kiểm tra các khả năng khác bằng cách quay lại). ví dụ: nếu bạn đang ở q1 và biểu tượng nhập hiện tại là 'a', bạn hãy chuyển sang trạng thái 4 và ngừng tính toán thêm.

đây là mã Python:

#nfa simulation for (a|b)*abb 
#state 4 is a trap state 


import sys 

def main(): 
    transition = [[[0,1],[0]], [[4],[2]], [[4],[3]], [[4],[4]]] 
    input = raw_input("enter the string: ") 
    input = list(input) #copy the input in list because python strings are immutable and thus can't be changed directly 
    for index in range(len(input)): #parse the string of a,b in 0,1 for simplicity 
     if input[index]=='a': 
      input[index]='0' 
     else: 
      input[index]='1' 

    final = "3" #set of final states = {3} 
    start = 0 
    i=0 #counter to remember the number of symbols read 

    trans(transition, input, final, start, i) 
    print "rejected" 



def trans(transition, input, final, state, i): 
    for j in range (len(input)): 
     for each in transition[state][int(input[j])]: #check for each possibility 
      if each < 4:        #move further only if you are at non-hypothetical state 
       state = each 
       if j == len(input)-1 and (str(state) in final): #last symbol is read and current state lies in the set of final states 
        print "accepted" 
        sys.exit() 
       trans(transition, input[i+1:], final, state, i) #input string for next transition is input[i+1:] 
     i = i+1 #increment the counter 


main() 

sản lượng mẫu: (chuỗi kết thúc với abb được chấp nhận)

enter the string: abb 
accepted 

enter the string: aaaabbbb 
rejected 

......