Դետերմինացված վերջավոր ավտոմատ - DFA

Դետերմինացված վերջավոր ավտոմատը (DFA) մի վիտուալ մեքենա է, որ բաղկացած է ղեկավարող սարքից, ինֆորմացիան կրող ժապավենից և ժապավենի հերթական բջջի նիշը կարդացող և ղեկավարող սարքին փոխանցող գլխիկից։

Դետերմինացված վերջավոր ավտոմատի վարքը սահմանվում է մի հնգյակով՝ \(A=\langle\Sigma, Q, q_0, F, \delta\rangle\), որտեղ \(\Sigma\)-ն ժապավենի վրա թուլատրված նիշերի բազմությունն է, \(Q\)-ն ղեկավարող սարքի ներքին վիճակների բազմությունն է, \(q_0\)-ն այն ներքին վիճակն է, որում ավտոմատը գտնվում է աշխատանքը սկսելու պահին, \(F\)-ը ճանաչող (հաստատող, թույլատրող) վիճակների բազմությունն է, որոնցում ավտոմատը կարող է դադարեցնել իր աշխատանքը, և \(\delta\)-ն \(Q\times\Sigma\to Q\) տիպի ֆունկցա է, որը ավտոմատի ներքին վիճակը փոխում է ըստ ընթերցող գլխիկի տված նիշի և ավտոմատի ընթացիկ ներքին վիճակի։

Օրինակ, «\(a^{+}b^{+}\)» կանոնավոր արտահայտությամբ որոշվող տողերը ճանաչող ավտոմատի համար \(\delta\) ֆունկցիան ունի հետևյալ տեսքը. \[ \delta(q_0,a)=q_1, \quad \delta(q_1,a)=1_1, \quad \delta(q_1,b)=q_2, \quad \delta(q_2,b)=q_2: \]
Համարվում է, որ ավտոմատը ճանաչել է նիշերի տրված հաջորդականությունը, եթե ընթերցող գլխիկը, դեպի աջ շարժվելով, ժապավենի վրա հասել է վերջին նիշին հաջորդող դիրքին և ավտոմատի ներքին վիճակը պատկանում է \(F\) բազմությանը։

Քանի որ ավտոմատի ընթերցող գլխիկը կարող է տեղաշարժվել միայն դեպի աջ, ապա ժապավենը կարելի է մոդելավորել ցուցակով, իսկ գլխիկի տեղաշարժը՝ ցուցակի հերթական տարրը հեռացնելով։ * * * Ավտոմատի մոդելի սահմանումը շատ պարզ է.

(defstruct automata
    alphabet    ; այբուբենի նիշերի բազմություն
    states      ; վիճակների բազմություն
    initial     ; սկզբնական վիճակ
    finals      ; ճանաչող վիճակների բազմություն
    commands    ; վիճակի փոփոխման ֆունկցիան
)

Օրինակ, վերը հիշատակված ավտոմատը նկարագրելու համար պետք է գրել.

(defvar *a0*
  (make-automata
    :alphabet '(#\a #\b)
    :states '(s0 s1 s2)
    :initial 's0
    :finals '(s2)
    :commands 
       '((s0 #\a . s1)
         (s1 #\a . s1)
         (s1 #\b . s2)
         (s2 #\b . s2))))

\(\delta\) ֆունկցիայի վարքը նկարագրող ցուցակի ամեն մի տարրը կետով ցուցակով է, որի առաջին երկու տարրերը ֆունկցիայի արգումենտներն են, իսկ երրորդը՝ արժեքը։ Ավտոմատի commands ատրիբուտի (սլոտի) մեջ տրված արգումենտներին համապատասխանող արժեքը որոնելու համար սահմանված ֆունկցիան պարզապես անցնում է ցուցակի տարրերով և վերադարձնում է անհրաժեշտ եռյակի երրորդ տարրը։ Եթե տրված արգումենտներին համապատասխանող եռյակ չկա, ապա վերադարձնում է nil։

(defun delta (au s c)
  (loop for tri in (automata-commands au)
        when (and (eql s (car tri)) (char= c (cadr tri)))
        do (return (cddr tri))))

Սահմանված ավտոմատը նիշերի տրված ցուցակի վրա գործարկելու համար պետք է կարդալ ժապավենի հերթական սիմվոլը, համադրել այն ավտոմատի ներքին վիճակի հետ և ավտոմատի հրամանների ցուցակում որոնել այդ զույգին համապատասխան եռյակը։ automata-run ֆունկցիան ավտոմատի ինտերպրետատորի ռեկուրսիվ իրականացումն է։

(defun automata-run (machine tape start)
  (let ((e (endp tape))
        (f (member start (automata-finals machine))))
    (cond
      ((and e f) t)
      ((and e (not f)) nil)
      (t (automata-run machine (cdr tape) (delta machine start (car tape)))))))

Այս ֆունկցիայի առաջին արգումենտը ավտոմատն է, երկրորդը՝ ժապավենը մոդելավորող ցուցակը, իսկ երրորդը՝ այն վիճակն է, որից պետք է սկսել ինտերպրետացիան։

Մի որևէ նիշերի տող ավտոմատով ճանաչելու համար պետք է տողի պարունակությունը գրել ժապավենի վրա և ավտոմատը գործարկել սկզբնական վիճակից։ Քանի որ ժապավենը մոդելավորված է ցուցակով, պիտի գրել մի մակրոս, որը ողը ձևափոխում է նիշերի ցուցակի․

(defmacro string-to-list (s)
  `(loop for c across ,s collect c))

recognize-with վերադարձնում է T, եթե տրված ավտոմատը ճանաչել է տրված տողը, և NIL՝ հակառակ դեպքում։

(defun recognize-with (machine cstring)
  (automata-run machine (string-to-list cstring) (automata-initial machine)))

Եվ ահա գործարկման մի քանի օրինակ․

(print (recognize-with *b* "0100"))
(print (recognize-with *b* "ab"))
(print (recognize-with *b* "aaaab"))
(print (recognize-with *b* "abbbbb"))
(print (recognize-with *b* "aaaabbbbb"))