ენების ჩომსკის იერარქია არის კლასიფიკაციის სისტემა, რომელიც ანაწილებს ფორმალურ გრამატიკებს მათი გენერაციული ძალის მიხედვით. ის შემოგვთავაზა ნოამ ჩომსკიმ, ცნობილმა ენათმეცნიერმა და კომპიუტერულმა მეცნიერმა, 1950-იან წლებში. იერარქია შედგება ოთხი დონისგან, თითოეული წარმოადგენს ფორმალური ენების განსხვავებულ კლასს. ეს დონეები ცნობილია როგორც Type-3 (რეგულარული), Type-2 (კონტექსტის გარეშე), Type-1 (კონტექსტზე მგრძნობიარე) და Type-0 (შეუზღუდავი).
იერარქიის ყველაზე დაბალ დონეზე გვაქვს ტიპი-3 ენები, რომლებიც ასევე ცნობილია როგორც რეგულარული ენები. ამ ენების ამოცნობა შესაძლებელია სასრული ავტომატებით, როგორიცაა დეტერმინისტული და არადეტერმინისტული სასრული ავტომატები. ჩვეულებრივ ენებს ახასიათებთ რეგულარული გამოთქმები და რეგულარული გრამატიკები. რეგულარული გამონათქვამები არის ალგებრული გამონათქვამები, რომლებიც აღწერს სტრიქონების ნიმუშებს, ხოლო რეგულარული გრამატიკა შედგება წარმოების წესებისგან, რომლებიც ქმნიან სტრიქონებს ჩვეულებრივ ენაზე. რეგულარული ენის მაგალითია ყველა სტრიქონის ნაკრები, რომელიც ემთხვევა მოცემულ რეგულარულ გამონათქვამს, მაგალითად, ყველა ორობითი სტრიქონის ენა ლუწი 0-ებით.
იერარქიაზე მაღლა ასვლისას ვხვდებით ტიპი 2 ენებს, რომლებიც ასევე ცნობილია როგორც კონტექსტური ენები. ამ ენების ამოცნობა შესაძლებელია pushdown ავტომატებით, რომლებიც არის სასრული ავტომატები, გაზრდილი სტეკით. კონტექსტის გარეშე ენები აღწერილია კონტექსტისგან თავისუფალი გრამატიკებით, რომლებიც შედგება წარმოების წესებისგან, რომლებიც ქმნიან სტრიქონებს კონტექსტისგან თავისუფალ ენაზე. კონტექსტისგან თავისუფალ გრამატიკებს აქვთ არატერმინალური სიმბოლოები, ტერმინალის სიმბოლოები და წარმოების წესები, რომლებიც აკონკრეტებენ, თუ როგორ შეიძლება შეიცვალოს არატერმინალები სიმბოლოების თანმიმდევრობით. კონტექსტისგან თავისუფალი ენის მაგალითია ყველა კარგად ჩამოყალიბებული არითმეტიკული გამონათქვამის ნაკრები, სადაც ფრჩხილები დაბალანსებულია და ოპერატორები სწორად გამოიყენება.
იერარქიის შემდეგი დონე არის Type-1 ენები, რომლებიც ასევე ცნობილია როგორც კონტექსტური მგრძნობიარე ენები. ამ ენების ამოცნობა შესაძლებელია წრფივი შემოსაზღვრული ავტომატებით, რომლებიც არის სასრული ავტომატები ლენტით, რომელსაც შეუძლია ორივე მიმართულებით მოძრაობა. კონტექსტზე მგრძნობიარე ენები აღწერილია კონტექსტზე მგრძნობიარე გრამატიკებით, რომლებიც შედგება წარმოების წესებისგან, რომლებიც ქმნიან სტრიქონებს კონტექსტზე მგრძნობიარე ენაზე. კონტექსტზე მგრძნობიარე გრამატიკებს აქვთ დამატებითი შეზღუდვა, რომ წარმოების წესის მარჯვენა მხარის სიგრძე არ შეიძლება იყოს უფრო მოკლე ვიდრე მარცხენა მხარის სიგრძე. კონტექსტზე მგრძნობიარე ენის მაგალითია ყველა პალინდრომის ნაკრები, სადაც სტრიქონი ერთნაირად იკითხება წინ და უკან.
დაბოლოს, იერარქიის ზედა ნაწილში გვაქვს Type-0 ენები, რომლებიც ასევე ცნობილია როგორც შეუზღუდავი ენები. ამ ენების ამოცნობა შესაძლებელია ტურინგის მანქანებით, რომლებიც აბსტრაქტული გამოთვლითი მოწყობილობებია, რომლებსაც შეუძლიათ ნებისმიერი კომპიუტერული ალგორითმის სიმულაცია. შეუზღუდავი ენები აღწერილია შეუზღუდავი გრამატიკებით, რომლებსაც არ აქვთ შეზღუდვები წარმოების წესებზე. შეუზღუდავი ენის მაგალითია ყველა რეკურსიულად დათვლადი ენების ნაკრები, რომელიც მოიცავს ყველა გამოთვლილ ენას.
ენების ჩომსკის იერარქია უზრუნველყოფს ფორმალური გრამატიკების კლასიფიკაციის სისტემატურ ჩარჩოს მათი გენერაციული ძალის მიხედვით. ის იწყება ჩვეულებრივი ენებით, რომლებიც ყველაზე ნაკლებად ძლიერია და პროგრესირებს კონტექსტის გარეშე, კონტექსტისადმი მგრძნობიარე და შეუზღუდავი ენებით, რომლებიც სულ უფრო მძლავრი ხდება. ეს იერარქია არის ფუნდამენტური კონცეფცია გამოთვლითი სირთულის თეორიის სფეროში და აქვს მნიშვნელოვანი გავლენა ფორმალური ენებისა და ავტომატების შესწავლაზე.
სხვა ბოლოდროინდელი კითხვები და პასუხები ჩომსკის იერარქია და მგრძნობიარე კონტექსტური ენები:
- რას ნიშნავს, რომ ერთი ენა მეორეზე ძლიერია?
- არსებობს ტიპი-0 ამოცნობის თანამედროვე მეთოდები? ველით თუ არა კვანტურ კომპიუტერებს ამის განხორციელებადს?
- აღწერეთ კონტექსტისადმი მგრძნობიარე გრამატიკის შემუშავების პროცესი ენისთვის, რომელიც შედგება სტრიქონებისგან თანაბარი რაოდენობის ერთი, ორი და სამი.
- მიეცით კონტექსტური მგრძნობიარე ენის მაგალითი და ახსენით, როგორ შეიძლება მისი ამოცნობა კონტექსტისადმი მგრძნობიარე გრამატიკით.
- რით განსხვავდება 0 ტიპის ენები, რომლებიც ასევე ცნობილია როგორც რეკურსიულად რიცხული ენები, სხვა ტიპის ენებისგან გამოთვლითი სირთულის თვალსაზრისით?
- ახსენით განსხვავება კონტექსტისგან თავისუფალ ენებსა და კონტექსტისადმი მგრძნობიარე ენებს შორის იმ წესების მიხედვით, რომლებიც მართავენ მათ ფორმირებას.