სასრული მანქანა

თავისუფალი ქართულენოვანი ენციკლოპედია ვიკიპედიიდან
გადასვლა: ნავიგაცია, ძიება


სასრული მანქანა ან სასრული ავტომატი — კომპიუტერული მეცნიერებების მათემატიკური მოდელი, რომელიც გამოიყენება როგორც კომპიუტერულ პროგრამებში, ასევე ალგორითმებსა და სხვადასხვა ლოგიკური სქემებში. ეს არის აბსტრაქტული მანქანა რომელსაც გააჩნია State-ები. ავტომატი არის მოცემულ დროს შესაბამის მდგომარეობაში. ის შეიძლება გადავიდეს ერთი მდგომარეობიდან მეორეში გარკვეულ დროს და ამას ეწოდება გარდამავლობა.

სასრული ავტომატების მოდელების გამოყენებით შესაძლებელია სხვადასხვა, უამრავი პრობლემების გადაჭრა, რომელთა შორისაა კომუნიკაციის პროტოკოლის დიზაინი, ენის დამუშავება (parsing) და სხვა საინჟინრო პროგრამები. ასევე დიდი გამოყენება აქვს ბიოლოგიისა და ხელოვნური ინტელექტში.

სასრული ავტომატის აბსტრაქტული მოდელი არის შედარებით სუსტი და არ გააჩნია ისეთივე ძალა, როგორიც აქვს სხვა მოდელებს, მაგალითად, როგირიცაა ტურინგის მანქანა. უფრო რომ დავაკონკრეტოთ, არსებობს ამოცანები რომელიც არ შეუძლია ამოხსნასას სასრულმა ავტომატმა, მაგრამ ეს შეუძლია ტურინგის მანქანას. გამომდინარე იქიდან, რომ სასრულ ავტომატს აქვს შეზღუდული მეხსიერება.

მაგალითი: ტურნიკეტი[რედაქტირება]

Torniqueterevolution.jpg

ტურნიკეტს აქვს ძალიან მარტივი მექანიზმი. მას გააჩნია სამი მოძრავი მხარი თანაბარ სიმაღლეზე. თავიდან არც ერთი არ მოძრაობს, ჩაკეტილ მდგომარეობაშია. როდესაც ხურდას ჩავაგდებთ მხარი გაიხსნება და აძლევს გამლვლელს საშუალებას დაატრიალოს 1/3 ით. ამის შემდეგ ტურნიკეტი ისევ დგება ჩაკეტილ მდგომარეოაბში და ელოდება ახალ გამსვლელს სანამ არ ჩააგდებს ხურდას.

ტურნიკეტს აქვს ორი მდგომარეობა(State) : ჩაკეტვა და გახსნა. მასზე მოქმედებს ორი შემავალი ინფორმაცია (input): ვაგდებთ ხურდას მხარი იხსნება,ხოლო დაკეტილი მდგომარეობაში კი არ რეაგირებს. ასევე არ აქვს მნიშვნელობა თუ რამდენჯერ მოხდება მხარის დატრიელება. როცა ხურდას ვაგდებთ, მანქანას შემავალი ინფორმაცია არის coin, ანუ დაკეტილიდან იცვლება ღიაზე. ასევე გახსნილ მდგომარეობაში არ აქვს მნიშვნელობა დავამატებთ თუ არა ხურდას, ანუ დამატებითი ხურდა არც ცვლის მანქანის მდგომარეობას, ხოლო დატრიალების შემდეგ უბრუნდება ჩაკეტილ მდგომარეობას. ტურნიკეტის მანქანა შეიძლება წარმოვადგინოთ ცხრილის სახით :

მიმდინარე მდგომარეობა შემომავალი ინფორმაცია შემდეგი მდგომარეობა გამომავალი ინფორმაცია
ჩაკეტილი ხურდა გახსნილი შესვლა შესაძლებელია
შესვლა დაკეტილი none
გახსნილი ხურდა გახსნილი none
შესვლა დაკეტილი შესვლა განხორციელდა

ეს ასევე შეიძლება წარმოვადგინოთ მიმათული გრაფით. თოთოეული მდგომარეობა იქნება გრაფის წვერო. წიბო გვიჩვენებს რომელი მდგომარეობდან რომელში გადადის. Turnstile state machine colored.svg

კლასიფიკაცია [რედაქტირება]

მანქანის მდგომარეობა შეიძლება დავყოთ ოთხ ძირითად სტადიად Transducers, Acceptors, Classifiers და Sequencers.

ენის მიღება და მისი ამოცნობა (Acceptors)[რედაქტირება]

Acceptors - ანუ მიმღები სტადია, გვაძლევს ორ პასუხს დიახ ან არა, იმისდა მიხედვით იღებს თუ არა მანქანა შემოსულ ინფორმაციას(input). ყველა სასრული მანქანა ამბობს შესაძლებელია თუ არა შემოსული ინფორმაციის მიღება. როცა შემოსული ინფორმაცია პროცესირდება ანუ დასრულდება, თუ მანქანის მდგომარეობა არის მიმღები (accepting state,) მაშინ იღებს მოცემულ ინფორმაციას, წინააღმდეგ შემთხვევაში უარყოფს ანუ აკეთებს reject-ს. როგორც წესი შემოსული ინფორმაცია ეს არის სიმბოლოები;თვალსაჩინოებისთვის განვიხილოთ (სურათი 2) .
Fsm parsing word nice.svg

მანქანა გვიჩვენებს რომ იღებს მხოლოდ ერთ სიტყვას „nice”. ანუ მიმღები სტადია ეს არის მხოლოდ ნომერი 7.

მანქანას ასევე შეუძლია განსაზღვროს ენა, რომლის შემცველ ყველა სიტყვას იღებს და უარყოფს ყველა დანარჩენს რომელიც არ შედის ამ ენაში. ამ შემთვევაში ჩვენ ვამბობთ რომ მანქანამ ეს ენა მიიღო. ყველა ენა რომელსაც სასრული მანქანა იღებს არის რეგულარული ენა - ენა არის რეგულარული თუ არსებობს რაღაც სასრული მანქანა რომელიც იღებს ამ ენას.

დამწყები სტადია[რედაქტირება]

დამწყები სტადია დიაგრამაზე გამოისახება მიმართული ისრით

საბოლოო სტადია[რედაქტირება]

მიმღები სტადია ან იგივე საბოლოო სტადია (final state or accepting state) გვაწვდის ინფორმაციას შემოსულ სტრინგზე და გვეუბნება, რომ ეს სტრინგი შედის თუ არა მოცემულ ენაში. ის ძირითად წარმოდგენილია ორი წრის საშუალებით. მაგალითისთვის განვიხილოთ დიაგრამა (სურათი 3):
DFAexample.svg
დეტერმინისტული სასრული მანქანა ამოწმებს შემოსული ორიბითი სტრინგი შეიცავს თუ არა ლუწი რაოდენობის 0-ებს. S1 არის საწყისი მდგომარეობა, რომელიც გვიჩვენებს, რომ მოცემულ სტადიაში არის ლუწი რაოდენობის 0-ები. S1 ამასთანვე არის მიმღები სტადიაც. ეს მანქანა მიიღებს შემოსულ სტრინგს მაშინ, როდესაც შემოსული ორობითი სტრინგი შეიცავს ლუწ რაონდების 0-ებს (იღებს ასევე თუ საერთოდ არ შედის 0). მაგალითად ეს მანქანა მიიღებს შემდეგის სახის სტრინგებს : 1, 111, 1111..., 00, 010, 1011101, და ა.შ.

დეტერმინისტული მანქანები[რედაქტირება]

დეტერმინისტულ მანქანაში თითეულ სტადიას აქვს მხოლოდ და მხოლოდ ერთი გადასვლა (transition) ყველა შესაძლო შემოსულ ინფორმაციაზე, ხოლო არა-დეტერმინისტულ მანქანაში, შემოსულმა ინფორმაცია შეიძლება გამოიწვიოს ერთი ან ერთზე მეტი ან საერთოდ არანაირი გადასხვა მოცემული სტადიისათვის. განსხვავება უფრო თვალსაჩინოა პრაქტიკაში და არა თეორიაში. არსებობს ალგორითმი, რომლის საშუალებითც, ნებისმიერი არა-დეტერმინისტული მანქანა შესაძლებელია გარდაიქმანას უფრო რთულ დეტერმინისტულ მანქანაზე.

მათემატიკური მოდელი[რედაქტირება]

ფორმალური განმარტება:

დეტერმინისტული სასრული მანქანას შედგება ხუთი ძირითადი ნაწილისაგან (Σ, S, s0 ,δ , F) სადაც :
 
  • ∑ არის შემომავალი ინფორმაცია ( რომელიც შედგება სასრული, არა ცარიელი სიმბოლოების სიმრავლისაგან)
  • S ეს არის სასრული სტადიების სიმრავლე
  • s0 საწყისი სტადია, რომელიც ეკუთვნის S-ს.
  • δ სტადიების გარდამავლობის ფუნქცია : δ : S x ∑ −> S ( არა-დეტერმინისტული მანქანისთვის იქნება : δ : S x ∑ −> P(S)
  • F არის საბოლოო სტადია, რომელიც ეკუთვნის S-ს.

როგორც დეტერმინისტულ ასევე არა-დეტერმინისტულ მანქანებში, ჩვეულებრივ δ არის ნაწილობრივი ფუნქცია ანუ δ(Q,X) არ არის განსზაღვრული Q Є S და X Є ∑ ამათი ყველა კონიბინაციისათვის. თუ რაღაც სასრული მანქანა M არის Q სტადიაში, შემდეგეი სიმბოლო არის X და δ(Q,X) არ არის განსაზღვრული, M მანქანა უარყოფს შემოსულ ინფორმაციას (ანუ მოცემულ input-ს აკეთებს reject-ს). ეს ნაკლებად გამოყენებადია როდესაც გვაქ მანქანის ტრანსფორმაცია, უფრო გამოიყენება ზოგად მანქანებში.

იხილეთ აგრეთვე[რედაქტირება]