კონტექსტის გარეშე ენა არის ფორმალური ენის ტიპი, რომლის აღწერა შესაძლებელია კონტექსტის თავისუფალი გრამატიკის გამოყენებით. გამოთვლითი სირთულის თეორიის სფეროში კონტექსტისგან თავისუფალი ენები მნიშვნელოვან როლს თამაშობენ პრობლემების სირთულის და გამოთვლის საზღვრების გაგებაში. კონტექსტისგან თავისუფალი ენის ცნების სრულად გასაგებად აუცილებელია მისი განმარტებისა და კონტექსტისგან თავისუფალი გრამატიკის კომპონენტების შესწავლა.
კონტექსტის გარეშე ენა განისაზღვრება, როგორც სტრიქონების ერთობლიობა, რომელიც შეიძლება შეიქმნას კონტექსტის გარეშე გრამატიკით. კონტექსტის გარეშე გრამატიკა შედგება ოთხი კომპონენტისგან: არატერმინალური სიმბოლოების ნაკრები, ტერმინალური სიმბოლოების ნაკრები, წარმოების წესების ნაკრები და საწყისი სიმბოლო.
არატერმინალური სიმბოლოები წარმოადგენს აბსტრაქტულ ერთეულებს, რომლებიც შეიძლება შემდგომ გაფართოვდეს ან შეიცვალოს სხვა სიმბოლოებით. ეს სიმბოლოები, როგორც წესი, წარმოდგენილია დიდი ასოებით. მაგალითად, არითმეტიკული გამონათქვამების კონტექსტის გარეშე გრამატიკაში შეიძლება გვქონდეს არატერმინალური სიმბოლოები, როგორიცაა E (გამოხატვა), T (ტერმინს წარმოადგენს) და F (ფაქტორს წარმოადგენს).
ტერმინალური სიმბოლოები კი, თავის მხრივ, ენის ელემენტარული ერთეულია. ამ სიმბოლოების შემდგომი გაფართოება შეუძლებელია და, როგორც წესი, წარმოდგენილია მცირე ასოებით ან სხვა სიმბოლოებით. არითმეტიკული გამონათქვამების კონტექსტში, ტერმინალის სიმბოლოები შეიძლება შეიცავდეს რიცხვებს (მაგ., 0, 1, 2) და არითმეტიკულ ოპერატორებს (მაგ., +, -, *, /).
წარმოების წესები განსაზღვრავს, თუ როგორ შეიძლება არატერმინალური სიმბოლოების გაფართოება ან ჩანაცვლება სხვა სიმბოლოებით. წარმოების თითოეული წესი შედგება არატერმინალური სიმბოლოსგან მარცხენა მხარეს და სიმბოლოების თანმიმდევრობისგან (როგორც არატერმინალური, ასევე ტერმინალური) მარჯვენა მხარეს. ეს წესები განსაზღვრავს შესაძლო გარდაქმნებს ან წარმოებულებს, რომლებიც შეიძლება გამოყენებულ იქნას ენაში სწორი სტრიქონების გენერირებისთვის. მაგალითად, არითმეტიკული გამონათქვამების კონტექსტის გარეშე გრამატიკაში შეიძლება გვქონდეს წარმოების წესები, როგორიცაა E -> E + T (მიუთითებს, რომ გამოხატვის გაფართოება შესაძლებელია ტერმინის დამატებით) ან T -> F (მიუთითებს, რომ ტერმინი შეიძლება იყოს შეცვალა ფაქტორი).
საწყისი სიმბოლო წარმოადგენს საწყის არატერმინალურ სიმბოლოს, საიდანაც იწყება მოქმედი სტრიქონების გენერაცია. ის ჩვეულებრივ აღინიშნება S-ით. არითმეტიკული გამონათქვამების კონტექსტში, საწყისი სიმბოლო შეიძლება იყოს E, რაც მიუთითებს, რომ სწორი გამონათქვამების გენერაცია იწყება გამოხატულებიდან.
კონტექსტის გარეშე ენისა და მისი კომპონენტების ცნების საილუსტრაციოდ, მოდით განვიხილოთ მარტივი კონტექსტის გარეშე გრამატიკა ენისთვის, რომელიც ქმნის დაბალანსებულ ფრჩხილებს. გრამატიკა შედგება შემდეგი კომპონენტებისგან:
არატერმინალური სიმბოლოები: S (დაწყების სიმბოლო)
ტერმინალის სიმბოლოები: (, )
წარმოების წესები: S -> (S) | SS | ε (სადაც ε წარმოადგენს ცარიელ სტრიქონს)
ამ გრამატიკაში არატერმინალური სიმბოლო S წარმოადგენს დაბალანსებული ფრჩხილების სტრიქონს. წარმოების წესები განსაზღვრავს, რომ S შეიძლება გაფართოვდეს სხვა S-ის ჩასმით ფრჩხილებში ((S)), ორი S-ის (SS) შეერთებით ან ცარიელი სტრიქონის (ε) გენერირებით.
ამ გრამატიკის გამოყენებით, ჩვენ შეგვიძლია შევქმნათ სწორი სტრიქონები დაბალანსებული ფრჩხილების ენაზე. მაგალითად, დაწყებული S სიმბოლოთი S-ით, შეგვიძლია გამოვიყენოთ წარმოების წესები სტრიქონის (()) გამოსაყვანად. ეს სტრიქონი წარმოადგენს დაბალანსებული ფრჩხილების თანმიმდევრობას.
კონტექსტის გარეშე ენა განისაზღვრება, როგორც სტრიქონების ერთობლიობა, რომელიც შეიძლება შეიქმნას კონტექსტის გარეშე გრამატიკით. კონტექსტის გარეშე გრამატიკის კომპონენტები მოიცავს არატერმინალურ სიმბოლოებს, ტერმინალის სიმბოლოებს, წარმოების წესებს და დაწყების სიმბოლოს. არატერმინალური სიმბოლოები წარმოადგენს აბსტრაქტულ ერთეულებს, რომლებიც შეიძლება გაფართოვდეს ან შეიცვალოს, ხოლო ტერმინალური სიმბოლოები ენის ელემენტარული ერთეულია. წარმოების წესები განსაზღვრავს შესაძლო გარდაქმნებს ან წარმოებულებს, ხოლო საწყისი სიმბოლო წარმოადგენს საწყის არატერმინალურ სიმბოლოს სწორი სტრიქონების გენერირებისთვის.
სხვა ბოლოდროინდელი კითხვები და პასუხები კონტექსტში მგრძნობიარე ენები:
- რას ნიშნავს, რომ ერთი ენა მეორეზე ძლიერია?
- ჩომსკის გრამატიკული ნორმალური ფორმა ყოველთვის გადასაწყვეტია?
- არსებობს ტიპი-0 ამოცნობის თანამედროვე მეთოდები? ველით თუ არა კვანტურ კომპიუტერებს ამის განხორციელებადს?
- D ენის მაგალითში რატომ არ მოქმედებს სატუმბი თვისება S = 0^P 1^P 0^P 1^P სტრიქონისთვის?
- რა ორი შემთხვევაა გასათვალისწინებელი სტრიქონის გაყოფისას სატუმბი ლემის გამოსაყენებლად?
- B ენის მაგალითში რატომ არ მოქმედებს ტუმბოს თვისება a^Pb^Pc^P სტრიქონისთვის?
- რა პირობები უნდა დაკმაყოფილდეს სატუმბი ქონების შესანარჩუნებლად?
- როგორ შეიძლება გამოყენებულ იქნას Pumping Lemma CFL-ებისთვის იმის დასამტკიცებლად, რომ ენა არ არის კონტექსტისგან თავისუფალი?
- რა პირობები უნდა დაკმაყოფილდეს იმისთვის, რომ ენა ჩაითვალოს კონტექსტისგან თავისუფლად, კონტექსტის თავისუფალი ენებისთვის სატუმბი ლემის მიხედვით?
- ახსენით რეკურსიის ცნება კონტექსტის გარეშე გრამატიკის კონტექსტში და როგორ იძლევა ის გრძელი სტრიქონების გენერირების საშუალებას.
იხილეთ მეტი კითხვები და პასუხები კონტექსტში მგრძნობიარე ენებში