ჩომსკის იერარქია

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

კომპიუტერულ მეცნიერებებში, კერძოდ ფორმალურ ენებში ჩომსკის იერარქია (ასევე ცნობილი, როგორც ჩომსკი–შუცენბერგერის იერარქია) არის ფორმალური გრამატიკების კლასთა იერარქია. ის აღწერა ნოამ ჩომსკიმ 1956 წელს[1], ხოლო მის სახელწოდებაში არის მარსელ–პოლ შუცენბერგერის გვარი, რადგან მან მნიშვნელოვანი როლი შეასრულა ფორმალური ენების განვითარებაში. ჩომსკის იერარქია საშუალებას აძლევს კომპიუტინგის სფეროს მოღვაწეებს ენებთან დაკავშირებულ პრობლემებს შეხედონ სისტემურად და მარტივად გადაჭრან ისინი.

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

ფორმალური გრამატიკა შედგება შემდეგი ელემენტებისგან:

პროდუქციის წესების სასრული სიმრავლე (გამოსახულების მარცხენა მხარე → გამოსახულების მარჯვენა მხარე) ქვემოთ მოყვანილია მაგალითი.

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

ტერმინალთა სასრული სიმრავლე. (ტერმინალი აღნიშნავს პროდუქციის საბოლოო შედეგის ერთ ნაწილს, ამ ტერმინალიდან ვერ დავიწყებთ ახალ პროდუქციას).

• საწყისი სიტყვა (სიმბოლო ან სიმბოლოები – უფრო ხშირად არატერმინალი)

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

როგორც წესი, არატერმინალები გამოისახება მაღალი რიგის (uppercase) სიმბოლოებით (დიდი სიმბოლოები, რომლებიც გამოიყენება მაგ. წინადადების დასაწყისში)

S \rightarrow \, ABS
S \rightarrow \, ε (სადაც ε არის ცარიელი სიმბოლო)
BA \rightarrow \, AB
BS \rightarrow \, b
Bb \rightarrow \, bb
Ab \rightarrow \, ab
Aa \rightarrow \, aa

ამ შემთხვევაში, საწყისი სიმბოლო S, აღწერს ყველა იმ სიტყვის ენას, რომელიც არის  a^n b^n ტიპის.

იერარქია[რედაქტირება]

The Chomsky hierarchy
Set inclusions described by the Chomsky hierarchy

იერარქია შედგება შემდეგი დონეებისაგან:

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

• პირველი დონის (გრამატიკა "მგრძნობიარე კონტექსტით"), რომელიც წარმოქმნის მგრძნობიარე კონტექსტის ენებს. ამ გრამატიკებს აქვთ წარმოქმნის შემდეგნაირი ფორმა: \alpha A\beta \rightarrow \alpha\gamma\beta, სადაც A არის არატერმინალი და \alpha, \beta და \gamma ტერმინალები და არატერმინალები. სიმბოლოთა მიმდევრობები: \alpha და \beta შეიძლება იყოს ცარიელი, თუმცა \gamma არ შეიძლება იყოს ცარიელი. გარდაქმნა S \rightarrow \epsilon დაშვებულია, თუ S არ არის მოცემული გრამატიკის არც ერთი წესის მარჯვენა მხარეში. ამ დონის გრამატიკებით აღწერილი ყველა ენის გაერთიანება არის ზუსტად ის სიმრავლე, რომელიც აღიქმება წრფივად შემოსაზღვრული ავტომატებით (არადეტერმინირებული ტურინგის მანქანა, რომლის მეხსიერება არის შემოსაზღვრული რაიმე მუდმივი რიცხვის შესატან მონაცემთა სიგრძეზე ნამრავლით).

• მეორე დონის (ტიპის) გრამატიკები თავისუფალი კონტექსტის გრამატიკები წარმოქმნიან თავისუფალი კონტექსტის ენებს. ისინი აღიწერებიან შემდეგი ფორმის წესებით: A \rightarrow \gamma, სადაც A არის არატერმინალი და \gamma არის სიმბოლოთა მიმდევრობა, რომელშიც თითოეული შეიძლება იყოს ტერმინალიც და არატერმინალიც. ამ ენათა სიმრავლე არის ზუსტად ის, რომელიც აღიქმება pushdown automaton–ით. თავისუფალი კონტექსტის ენები, ანუ დეტერმინირებული თავისუფალი კონტექსტის ენები არიან თეორიული ბაზისი თითქმის ყველა პროგრამირების ენისა, მიუხედავად იმისა, რომ მათი სინტაქსი ასევე შეიცავს მგრძნობიარე კონტექსტის სახელებს. ხშირად გრამატიკების ქვესიმრავლეები გამოიყენება გადარჩევის(parsing) გასაიოლებლად, მაგ. LL parser.

• მესამე დონის (ტიპის) გრამატიკები რეგულარული გრამატიკები წარმოქმნიან რეგულარულ ენებს. ამ გრამატიკებს აქვთ შემდეგი შეზღუდვები: მათ აქვთ მხოლოდ ერთი არატერმინალი მარცხენა მხარეს, ხოლო მარჯვენა მხარე შედგება ერთი ტერმინალისაგან, რომელსაც შეიძლება მოსდევდეს(მარჯვენა რეგულარული) ან წინ უსწრებდეს(მარცხენა რეგულარული) არატერმინალი. ორივე შემთხვევა წარმოქმნის ერთიდაიგივე ენებს, თუმცა თუ მათ წესებს კომბინირებულად გამოვიყენებთ, მიღებული ენა არ იქნება რეგულარული. წესი S \rightarrow \epsilon დასაშვებია, თუ S არ არის გრამატიკის არც ერთი წესის მარჯვენა მხარეს. ამ გრამატიკებით მიიღება ენათა სიმრავლე, რომელიც გადაიჭრება სასრული ავტომატებით, ამასთან, ეს სიმრავლე შეიძლება მივიღოთ რეგულარული ჩანაწერებით. რეგულარული ენები გამოიყენება პროგრამირების ენებში ძებნის მოდელებისა და ლექსიკური სტრუქტურების აღსაწერად.

აღსანიშნავია, რომ გრამატიკათა ის ნაწილი, რომელიც შეესაბამება რეკურენტულ ენებს, არ არის ამ იერარქიაში; ეს ნაწილი მოთავსებულია პირველ და მეორე დონეებს შორის.

რეზიუმე:

ყველა რეგულარული ენა არის თავისუფალი კონტექსტის;
ყველა თავისუფალი კონტექსტის ენა, რომელიც არ შეიცავს ცარიელ სიმბოლოს, არის მგრძნობიარე კონტექსტის;
ყველა მგრძნობიარე კონტექსტის ენა არის რეკურენტული;
ყველა რეკურენტული ენა არის რეკურსიულად თვლადი;

სხვაგვარად რომ ვთქვათ, არსებობს რეკურსიულად თვლადი ენები, რომლებიც არ არიან თავისუფალი კონტექსტის;
არსებობს მგრძნობიარე კონტექსტის ენები, რომლებიც არ არიან თავისუფალი კონტექსტის;
არსებობს თავისუფალი კონტექსტის ენები, რომლებიც არ არიან რეგულარული;

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

გრამატიკა ენები ავტომატები წარმოების წესები (შეზღუდვები)
ნულოვანი დონის რეკურსიულად გადათვლადი ტურინგის მანქანა \alpha \rightarrow \beta (არაა შეზღუდვები)
პირველი დონის მგრძნობიარე კონტექსტი წრფივად შემოსაზღვრული არადეტერმინირებული ტურინგის მანქანა \alpha A \beta \rightarrow \alpha \gamma \beta
მეორე დონის თვისუფალი კონტექსტი არადეტერმინირებული pushdown automaton A \rightarrow \gamma
მესამე დონის რეგულარული სასრული ავტომატი A \rightarrow a
and
A \rightarrow aB

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

  1. Chomsky, Noam (1956). „Three models for the description of language“. IRE Transactions on Information Theory (2): გვ. 113–124. DOI:10.1109/TIT.1956.1056813. 
  • Chomsky, Noam (1959). „On certain formal properties of grammars“. Information and Control 2 (2): გვ. 137–167. DOI:10.1016/S0019-9958(59)90362-6. 
  • Chomsky, Noam; Schützenberger, Marcel P. (1963). "The algebraic theory of context free languages", რედ. Braffort, P.; Hirschberg, D.: Computer Programming and Formal Languages. Amsterdam: North Holland, გვ. 118–161. 
  • Davis, Martin E.; Sigal, Ron; Weyuker, Elaine J. (1994). Computability, complexity, and languages: Fundamentals of theoretical computer science. Boston: Academic Press, Harcourt, Brace, გვ. 327. ISBN 0-12-206382-1. 

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