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

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

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

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

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

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

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

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

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

როგორც წესი, არატერმინალები გამოისახება მაღალი რიგის (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}$ ტიპის.

იერარქია

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$

სქოლიო

• Chomsky, Noam (1959). „On certain formal properties of grammars“ (PDF). Information and Control. 2 (2): 137–167. doi:10.1016/S0019-9958(59)90362-6. დაარქივებულია ორიგინალიდან (PDF) — 2015-09-23. ციტირების თარიღი: 2013-06-30.
• 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. 

რესურსები ინტერნეტში

• http://www.staff.ncl.ac.uk/hermann.moisl/ell236/lecture5.htm