Saturday, January 25, 2014

Դետերմինացված վերջավոր ավտոմատ - 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"))

Monday, January 6, 2014

Հիշող սարք և տեստային ալգորիթմ

Ուսանողական առաջադրանքներից մեկում ես հանձնարարել էի գրել մի կոմպիլյատոր, որը թվային հիշող սարքի և տեստավորման ալգորիթմի տեքստային ներկայացումից կոմպիլյացնում է տեստավորող մեքենային կոդ։ Նկարագրման լեզվի քերականությունը մոտավորապես հետևյալն էր․
     script = { memory | algorithm | test }.
     memory = 'Memory' IDENT '{' 'Rows' '=' NUMBER 'Columns' '=' NUMBER '}'.
  algorithm = 'Algorithm' IDENT '{' { element } '}'.
    element = ('->'|'<-') '(' operation {',' operation } ')'.
  operation = (W|R)('0'|'1').
       test = 'Test' IDENT 'With' IDENT.
Այս քերականությամբ, օրինակ, կարելի է նկարագրել \(3\times2\) չափի հիշողության մատրից և նրա վրա գործարկել \(\Uparrow(W0);\Downarrow(W1,R1)\) պարզագույն տեստը։
  Memory r3c2 {
    Rows = 3
    Columns = 2
  }

  Algorithm A0 {
    ->(W0)
    <-(W1,R1)
  }

  Test r3c2 With A0
Այս սկրիպտի կոմպիլյացիայից հետո պետք է կառուցվեր տեստավորող մեքենայի՝ սիմուլյատորի մի այստպիսի կոդ․
  0 0 W 0
  0 1 W 0
  1 0 W 0
  1 1 W 0
  2 0 W 0
  2 1 W 0
  0 0 W 1
  0 0 R 1
  0 1 W 1
  0 1 R 1
  1 0 W 1
  1 0 R 1
  1 1 W 1
  1 1 R 1
  2 0 W 1
  2 0 R 1
  2 1 W 1
  2 1 R 1
Քառյակի առաջին տարրը տողի հասցեն է, երկրորդը՝ սյան, երրորդ տարրը գործողությունն է՝ W - գրել, R - կարդալ, չորրորդ տարրը գործողության արգումենտն է։

Այս քառյակները հիշողության սարքի մոդելի վրա սիմուլյացնելու համար պետք է նախ՝ ստեղծել փչացած բջիջներ պարունակող հիշողության մոդել, ապա քառյակների սիմուլյացիայի արդյունքում պարզել, թե որ հասցեում է տեստավորման ալգորիթմը ձախողվում։
* * *
Սիմուլյատորի հիմնական գաղափարը հիշող սարքի բջիջն է, որում կարելի արժեք արժեք գրել և կարդալ սպասվող արժեք։ Այդ երկու գործողություններն ունեն այսպիսի ինտերֆեյս.
(defgeneric write-cell (c v))
(defgeneric read-cell (c))
Ճիշտ աշխատող բջիջը նկարագրել եմ cell անունով դասով․
(defclass cell ()
  ((value :initform 0
          :initarg :value
          :accessor cell-value)))
Որի համար գրելու գործողությունը տրված արժեքը վերագրում է value սլոտին, իսկ կարդալու գործողությունը վերադարձնում է value սլոտի արժեքը։
(defmethod write-cell ((c cell) v)
  (setf (cell-value c) v))
(defmethod read-cell ((c cell) v)
  (cell-value c))
Որպես օրինակ cell դասն ընդլայնել եմ և ստեղծել եմ cell-co դասը, որի կարդալու գործողությունը միշտ վերադարձնում է նախապես տրված հաստատուն արժեքը։
(defclass cell-co (cell) 
  ((coval :initform 0
          :initarg :coval
          :accessor cell-co-val)))

(defmethod read-cell ((c cell-co) v)
  (cell-co-val c))
Հիշող սարքի մոդելը երեք սլոտներով մի ստրուկտուա է․
(defstruct memory
  (rows 0)
  (columns 0)
  (matrix nil))
Հիշողության մոդելի կոնստրուկտորը մատրիցի բջիջները լրացնում է cell դասի օբյեկտներով։
(defun create-memory (row col)
  (let ((res (make-memory :rows row :columns col
                          :matrix (make-array (list row col)))))
    (dotimes (r (memory-rows res))
      (dotimes (c (memory-columns res))
        (setf (aref (memory-matrix res) r c)
              (make-instance 'cell :value 0))))
    res))
Հիշողության մոդելի համար նույնպես իրականացրել եմ գրելու և կարդալու գործողությունները։ Գրելու գործողությունը տրված արժեքը գրում է մատրիցի տրված կոորդինատներով բջջի մեջ, իսկ կարդալու գործողությունը տրված արժեքը համեմատում է մատրիցի տրված բջջի արժեքի հետ։ Քանի որ սա տեստավորման ալգորիթմները փորձարկելու համար նախատեսված մոդել է, այսպիսի վարքը լրիվ արդարացված է։
(defmethod write-memory ((m memory) r c v)
  (write-cell (aref (memory-matrix m) r c) v))
(defmethod read-memory ((m memory) r c v)
  (= (read-cell (aref (memory-matrix m) r c)) v))
Կոմպիլյացված ալգորիթմը հիշող սարքի մոդելի վրա գործարկելու համար նախատեսել եմ run-algorithm-on ֆունկցիան։ Այն արգումենտում ստանում է հիշողության մոդելը և քառյակների ֆայլը։
(defun run-algorithm-on (mem alg)
  (dolist (co (read-whole-algorithm alg))
    (let ((r (first co)) (c (second co)) (a (fourth co)))
      (if (eql 'W (third co))
        (write-memory mem r c a)
        (unless (read-memory mem r c a)
          (format t "ՍԽԱԼ։ Տեստը ձախողվեց (~D, ~D) բջջի վրա։~%" r c))))))
run-algorithm-on ֆունկցիայում քառյակների ֆայլը բեռնվում է որպես Lisp լեզվի ցուցակ read-whole-algorithm ֆունկցիայով։
(defun read-whole-algorithm (src)
  (labels
    ((read-one-command (cs)
       (let ((s (read-line cs nil)))
         (when s
           (read-from-string (concatenate 'string "(" s ")")))))
     (read-all-commands (cs res)
       (let ((c (read-one-command cs)))
         (if (null c)
           res
           (read-all-commands cs (cons c res))))))
  (with-open-file (inp src :direction :input)
    (reverse (read-all-commands inp '())))))
Հիմա մի օրինակ։ Ենթադրենք \(3\times2\) չափի հիշողության \((1,1)\) բջիջը անսարք է և բոլոր կարդալու գործողությունների ժամանակ վերադարձնում է \(0\) արժեքը։
(defvar *m* (create-memory 3 2))
(setf (aref (memory-matrix *m*) 1 1) (make-instance 'cell-co :coval 0))
(run-algorithm-on *m* "test1.alg")
Վերը բերված ալգորիթմը փչացած բջջով մոդելի վրա աշխատեցնելուց հետո ստանում եմ այսպիսի պատասխան․
ՍԽԱԼ։ Տեստը ձախողվեց (1, 1) բջջի վրա։
Որից երևում է, որ ալգորիթմը բջնում է անսարքությունը և սիմուլյատորն էլ անում է իր գործը։