हास्केल में परिमित automaton

Question

हास्केल में परिमित automaton का प्रतिनिधित्व करने का एक अच्छा तरीका क्या है? इसका डेटा प्रकार कैसा दिखता है?

हमारे कॉलेज में, ऑटोमेटा

(Q, X, delta, q_0, F) 

जहां क्यू automaton के राज्यों का सेट है, एक्स वर्णमाला (इस भाग भी necessery है), डेल्टा संक्रमण समारोह ले जा रहा है है एक 5 टपल के रूप में परिभाषित किया गया 2-ट्यूपल (क्यू, एक्स) और लौटने वाले राज्य/-s (गैर-निर्धारिती संस्करण में) और एफ स्वीकार्य/अंत राज्यों का सेट है।

सबसे महत्वपूर्ण बात, मुझे यकीन है कि किस प्रकार delta होना चाहिए नहीं कर रहा हूँ ...

Answer 1

दो मूल विकल्प हैं:

• एक स्पष्ट समारोह delta :: Q -> X -> Q (या [Q] के रूप में उपयुक्त) स्वेन हैगर पता चलता है के रूप में ।
• एक मानचित्र delta :: Map (Q, X) Q उदा। Data.Map का उपयोग करके, या यदि आपके राज्य/वर्णमाला आरोही संख्या Data.Array या Data.Vector द्वारा अनुक्रमित किया जा सकता है।

ध्यान दें कि इन दो दृष्टिकोण अनिवार्य रूप से बराबर हैं, एक नक्शा संस्करण एक समारोह संस्करण में से (एक अतिरिक्त Maybe के कारण lookup कॉल से थोड़ा अलग है) में बदल सकते हैं अपेक्षाकृत आसानी से

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

(या लुक-अप समारोह के उचित रूप से curried संस्करण जो कुछ मानचित्रण प्रकार के लिए प्रयोग कर रहे हैं।)

---

आप ऑटो का निर्माण कर रहे हैं संकलन समय पर माता (और इसलिए संभावित राज्यों को जानते हैं और उन्हें डेटा प्रकार के रूप में एन्कोड किया जा सकता है), फिर फ़ंक्शन संस्करण का उपयोग करके आपको बेहतर प्रकार की सुरक्षा मिलती है, क्योंकि संकलक यह सत्यापित कर सकता है कि आपने सभी मामलों को कवर किया है।

आप रन टाइम (जैसे उपयोगकर्ता इनपुट से) पर ऑटोमेटा के निर्माण कर रहे हैं तो एक नक्शे के रूप में delta भंडारण (और संभवतः के रूप में ऊपर समारोह रूपांतरण कर रही है) और एक उचित इनपुट सत्यापन गारंटी देता है कि शुद्धता होने ताकि fromJust सुरक्षित है (यानी किसी भी संभावित (Q,X) टुपल के लिए मानचित्र में हमेशा एक प्रविष्टि होती है और इसलिए लुक-अप कभी विफल नहीं होता है (कभी भी Nothing नहीं देता))।

गैर नियतात्मक ऑटोमेटा नक्शा विकल्प के साथ अच्छी तरह से काम करते हैं, क्योंकि एक असफल लुक-अप करने के लिए जाने के लिए कोई राज्य जैसा ही होता है, यानी एक खाली [Q] सूची है, और इसलिए वहाँ होने की जरूरत नहीं है किसी भीMaybe पर join . maybeToList (joinData.Monad और maybeToList से Data.Maybe से Maybe की विशेष हैंडलिंग)।

---

एक अलग नोट पर, वर्णमाला सबसे निश्चित रूप से आवश्यक है: यह है कि automaton इनपुट प्राप्त करता है।

Answer 2

"तीर" पैकेज में Control.Arrow.Transformer.Automaton मॉड्यूल देखें।यह प्रकार

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

यह थोड़ा उलझन में है क्योंकि यह एक तीर ट्रांसफार्मर है। सबसे सरल मामले में आप

type Auto = Automaton (->) 

जो अंतर्निहित तीर के रूप में कार्य करता है। स्थानापन्न (->) के लिए "एक" Automaton परिभाषा और इन्फ़िक्स अंकन का उपयोग आप देख सकते हैं इस मोटे तौर पर के बराबर है:

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

दूसरे शब्दों में एक automaton एक समारोह है कि एक इनपुट लेता है और एक परिणाम देता है और है एक नया automaton।

आप प्रत्येक राज्य के लिए एक फ़ंक्शन लिखकर सीधे इसका उपयोग कर सकते हैं जो तर्क लेता है और परिणाम और अगला कार्य देता है। उदाहरण के लिए, रेगेक्सपी "ए + बी" (यानी, कम से कम एक 'ए' की श्रृंखला 'बी' के बाद पहचानने के लिए एक राज्य मशीन है। (नोट: अपरीक्षित कोड)

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) 

अपने मूल प्रश्न, क्यू = {state1, state2}, एक्स = चार के संदर्भ में, डेल्टा समारोह अनुप्रयोग है, और एफ एक की तुलना में लौटने यह सच है (न कि राज्य संक्रमण है "राज्य स्वीकार करना" मैंने एक स्वीकार्य मूल्य के साथ एक आउटपुट संक्रमण का उपयोग किया है)।

वैकल्पिक रूप से आप तीर नोटेशन का उपयोग कर सकते हैं। Automaton लूप और सर्किट समेत सभी रोचक तीर कक्षाओं का एक उदाहरण है, ताकि आप देरी का उपयोग करके पिछले मानों तक पहुंच प्राप्त कर सकें। (नोट: फिर, अपरीक्षित कोड)

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') 

"देरी" तीर का मतलब है कि "पिछला" वर्तमान मान "सी" के पिछले मूल्य के बजाय के बराबर है। आप "आरईसी" का उपयोग कर अपने पिछले आउटपुट तक पहुंच भी प्राप्त कर सकते हैं। उदाहरण के लिए, यहां एक तीर है जो आपको समय के साथ एक क्षीण कुल देता है। (वास्तव में इस मामले में जांच की)

-- | 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 

नोट कैसे "देरी" के लिए इनपुट "वी", इसके उत्पादन से प्राप्त एक मूल्य भी शामिल है। "आरईसी" खंड इसे सक्षम बनाता है, इसलिए हम एक फीडबैक लूप बना सकते हैं।