Automaton hữu hạn trong Haskell

Question

Cách tốt nhất để đại diện cho automaton hữu hạn trong Haskell là gì? Kiểu dữ liệu của nó trông như thế nào?

Ở trường đại học của chúng tôi, automata được định nghĩa là một 5-tuple

(Q, X, delta, q_0, F) 

nơi Q là tập hợp của các quốc gia automaton của, X là bảng chữ cái (là phần này thậm chí necessery), đồng bằng là chức năng chuyển tiếp lấy 2-tuple từ (Q, X) và trạng thái trả về/-s (trong phiên bản không xác định) và F là tập hợp các trạng thái chấp nhận/kết thúc.

Quan trọng nhất, tôi không chắc chắn về loại delta nên có ...

Answer 1

Có hai lựa chọn cơ bản:

• Một chức năng rõ ràng delta :: Q -> X -> Q (hoặc [Q] nếu thích hợp) như Sven Hager gợi ý .
• Bản đồ delta :: Map (Q, X) Q ví dụ: sử dụng Data.Map hoặc nếu tiểu bang/bảng chữ cái của bạn có thể được lập chỉ mục theo số tăng dần Data.Array hoặc Data.Vector.

Lưu ý rằng hai cách tiếp cận cơ bản là tương đương, người ta có thể chuyển đổi từ phiên bản bản đồ đến một phiên bản chức năng (điều này là hơi khác nhau do thêm một Maybe từ lookup cuộc gọi) tương đối dễ dàng

delta_func q x = Data.Map.lookup (q,x) delta_map 

(Hoặc phiên bản được điều chỉnh phù hợp của chức năng tra cứu cho bất kỳ loại bản đồ nào bạn đang sử dụng.)

---

Nếu bạn đang xây dựng ô tô mata tại thời gian biên dịch (và vì vậy biết các trạng thái có thể và có thể mã hóa chúng như một kiểu dữ liệu), sau đó sử dụng phiên bản hàm cho bạn an toàn kiểu tốt hơn, vì trình biên dịch có thể xác minh rằng bạn đã bao phủ tất cả các trường hợp.

Nếu bạn đang xây dựng automata tại thời gian chạy (ví dụ như từ đầu vào của người dùng), sau đó lưu trữ delta làm bản đồ (và có thể thực hiện chuyển đổi chức năng như trên) và có xác nhận hợp lệ đầu vào đảm bảo tính chính xác sao cho fromJust an toàn (tức là luôn luôn có một mục nhập trong bản đồ cho bất kỳ bộ sưu tập nào có thể là (Q,X) và vì vậy việc tra cứu không bao giờ thất bại (không bao giờ trả về Nothing)).

Không xác định công việc automata tốt với tùy chọn bản đồ, bởi vì một thất bại nhìn lên cũng giống như không có nhà nước để đi đến, tức là một danh sách [Q] trống rỗng, và do đó không cần phải bất kỳ xử lý đặc biệt của Maybe ngoài cuộc gọi tới join . maybeToList (join là từ Data.Monad và maybeToList là từ Data.Maybe).

---

Trên một lưu ý khác, bảng chữ cái chắc chắn là cần thiết nhất: đó là cách tự động nhận đầu vào.

Answer 2

Kiểm tra mô-đun Control.Arrow.Transformer.Automaton trong gói "mũi tên".Loại trông giống như thế này

newtype Automaton a b c = Automaton (a b (c, Automaton a b c)) 

Điều này hơi khó hiểu vì máy biến áp mũi tên. Trong trường hợp đơn giản nhất, bạn có thể viết

type Auto = Automaton (->) 

Chức năng sử dụng nào làm mũi tên cơ bản. Thay (->) cho "a" trong định nghĩa Automaton và sử dụng ký hiệu ghi vào bạn có thể thấy điều này là tương đương với:

newtype Auto b c = Automaton (b -> (c, Auto b c)) 

Nói cách khác một automaton là một chức năng mà phải mất một đầu vào và trả về kết quả và một automaton mới.

Bạn có thể sử dụng điều này trực tiếp bằng cách viết hàm cho mỗi trạng thái lấy đối số và trả về kết quả và hàm tiếp theo. Ví dụ, đây là một máy trạng thái để nhận ra regexp "a + b" (có nghĩa là, một chuỗi ít nhất một 'a' theo sau là 'b'). (Lưu ý: Mã chưa được kiểm tra)

state1, state2 :: Auto Char Bool 
state1 c = if c == 'a' then (False, state2) else (False, state1) 
state2 c = case c of 
       'a' -> (False, state2) 
       'b' -> (True, state1) 
       otherwise -> (False, state1) 

Về câu hỏi của bạn ban đầu, Q = {state1, state2}, X = Char, đồng bằng là ứng dụng chức năng, và F là chuyển trạng thái trở về True (chứ không phải là có một "chấp nhận trạng thái" Tôi đã sử dụng quá trình chuyển đổi đầu ra với giá trị chấp nhận).

Hoặc bạn có thể sử dụng ký pháp Arrow. Automaton là một thể hiện của tất cả các lớp mũi tên thú vị, bao gồm Loop và Circuit, vì vậy bạn có thể truy cập vào các giá trị trước đó bằng cách sử dụng độ trễ. (Lưu ý: một lần nữa, mã chưa được kiểm tra)

recognise :: Auto Char Bool 
recognise = proc c -> do 
    prev <- delay 'x' -< c -- Doesn't matter what 'x' is, as long as its not 'a'. 
    returnA -< (prev == 'a' && c == 'b') 

Mũi tên "trì hoãn" có nghĩa là "trước" bằng giá trị trước đó của "c" thay vì giá trị hiện tại. Bạn cũng có thể truy cập vào đầu ra trước đó của bạn bằng cách sử dụng "rec". Ví dụ: đây là mũi tên cung cấp cho bạn tổng số phân rã theo thời gian. (Thực tế được kiểm tra trong trường hợp này)

-- | Inputs are accumulated, but decay over time. Input is a (time, value) pair. 
-- Output is a pair consisting 
-- of the previous output decayed, and the current output. 
decay :: (ArrowCircuit a) => NominalDiffTime -> a (UTCTime, Double) (Double, Double) 
decay tau = proc (t2,v2) -> do 
     rec 
     (t1, v1) <- delay (t0, 0) -< (t2, v) 
     let 
      dt = fromRational $ toRational $ diffUTCTime t2 t1 
      v1a = v1 * exp (negate dt/tau1) 
      v = v1a + v2 
     returnA -< (v1a, v) 
    where 
     t0 = UTCTime (ModifiedJulianDay 0) (secondsToDiffTime 0) 
     tau1 = fromRational $ toRational tau 

Lưu ý cách đầu vào "trì hoãn" bao gồm "v", giá trị bắt nguồn từ đầu ra của nó. Mệnh đề "rec" cho phép điều này, vì vậy chúng ta có thể xây dựng một vòng phản hồi.