შეგვიძლია განვსაზღვროთ, მიღებულია თუ არა მოცემული სტრიქონი კონტექსტის გარეშე გრამატიკით? გადასაწყვეტია ეს პრობლემა?
იმის დადგენა, მიღებულია თუ არა მოცემული სტრიქონი კონტექსტისგან თავისუფალი გრამატიკით, არის ფუნდამენტური პრობლემა გამოთვლითი სირთულის თეორიაში. ეს პრობლემა მიეკუთვნება გადაწყვეტილების უფრო ფართო კატეგორიას, რომელიც ეხება იმის დადგენას, არის თუ არა კონკრეტული საკუთრება მოცემული შეყვანისთვის. კონტექსტისგან თავისუფალი გრამატიკების შემთხვევაში, სტრიქონების მიღების პრობლემა მართლაც გადასაწყვეტია.
კონტექსტის გარეშე გრამატიკა არის ფორმალური სისტემა, რომელიც შედგება წარმოების წესების ნაკრებისგან, რომელიც აღწერს ენაზე სტრიქონების გენერირებას. იგი განისაზღვრება ტოპებით (V, Σ, R, S), სადაც V არის არატერმინალური სიმბოლოების ნაკრები, Σ არის ტერმინალური სიმბოლოების ნაკრები, R არის წარმოების წესების ნაკრები და S არის საწყისი სიმბოლო. კონტექსტის გარეშე გრამატიკის მიერ გენერირებული ენა არის ყველა სტრიქონის ნაკრები, რომელიც შეიძლება გამოვიდეს საწყისი სიმბოლოდან წარმოების წესების გამოყენებით.
იმის დასადგენად, მიღებულია თუ არა მოცემული სტრიქონი კონტექსტის გარეშე გრამატიკით, შეგვიძლია გამოვიყენოთ სხვადასხვა ალგორითმები, როგორიცაა CYK ალგორითმი ან Earley ალგორითმი. ეს ალგორითმები იყენებენ დინამიურ პროგრამირების ტექნიკას, რათა ეფექტურად შეამოწმონ, შესაძლებელია თუ არა სტრიქონის გამოყვანა გრამატიკის საწყისი სიმბოლოდან.
მაგალითად, CYK ალგორითმი აყალიბებს ცხრილს, სადაც თითოეული უჯრედი წარმოადგენს შეყვანის სტრიქონის ქვესტრიქონს და არატერმინალების ერთობლიობას, რომლებსაც შეუძლიათ ამ ქვესტრიქონის გენერირება. გრამატიკის წარმოების წესების საფუძველზე ცხრილის განმეორებითი შევსებით, ალგორითმი განსაზღვრავს, შეუძლია თუ არა დაწყების სიმბოლოს მთელი შეყვანის სტრიქონის გენერირება. თუ დაწყების სიმბოლო გამოჩნდება ცხრილის ზედა მარჯვენა უჯრედში, მაშინ სტრიქონი მიიღება გრამატიკაში; წინააღმდეგ შემთხვევაში, ეს არ არის.
განვიხილოთ შემდეგი მაგალითი: ვთქვათ, გვაქვს კონტექსტის გარეშე გრამატიკა წარმოების წესებით:
S -> AB
A -> a
B -> ბ
თუ გვინდა განვსაზღვროთ არის თუ არა სტრიქონი "ab" მიღებული ამ გრამატიკით, შეგვიძლია გამოვიყენოთ CYK ალგორითმი. ალგორითმი აყალიბებს ცხრილს ორი უჯრედით, ერთი შეყვანის სტრიქონის თითოეული სიმბოლოსთვის. ცხრილი ასე გამოიყურება:
| 1 | 2 |
—+—+—+
1 | A | S |
—+—+—+
2 | | B |
—+—+—+
ქვედა მწკრივიდან დაწყებული, ჩვენ ვხედავთ, რომ უჯრედი (2,2) შეიცავს არატერმინალს B, რომელიც წარმოიქმნება წარმოების წესით B -> b. ზედა მწკრივზე ასვლისას აღმოვაჩენთ, რომ უჯრედი (1,2) შეიცავს არატერმინალ S-ს, რომელიც წარმოიქმნება წარმოების წესით S -> AB. და ბოლოს, უჯრედი (1,1) შეიცავს არატერმინალს A, რომელიც წარმოიქმნება წარმოების წესით A -> a. ვინაიდან დაწყების სიმბოლო S ჩანს ზედა მარჯვენა უჯრედში, შეგვიძლია დავასკვნათ, რომ სტრიქონი "ab" მიღებულია გრამატიკაში.
პრობლემა იმის დადგენა, არის თუ არა მოცემული სტრიქონი მიღებული კონტექსტისგან თავისუფალი გრამატიკით, გადასაწყვეტია. ალგორითმები, როგორიცაა CYK ალგორითმი ან Earley ალგორითმი, შეიძლება გამოყენებულ იქნას ეფექტურად შესამოწმებლად, შესაძლებელია თუ არა სტრიქონის მიღება გრამატიკის საწყისი სიმბოლოდან. ეს ალგორითმები იყენებენ დინამიურ პროგრამირების ტექნიკას ცხრილების ასაგებად და სტრიქონის მიღების დასადგენად.
სხვა ბოლოდროინდელი კითხვები და პასუხები გადაწყვეტილების მიღება:
- შეიძლება თუ არა ლენტი შემოიფარგლოს შეყვანის ზომით (რაც ექვივალენტურია ტურინგის მანქანის ხელმძღვანელის შეზღუდული TM ფირის შეყვანის მიღმა გადაადგილებით)?
- რას ნიშნავს ტურინგის მანქანების სხვადასხვა ვარიაციები გამოთვლით შესაძლებლობებში ექვივალენტური იყოს?
- შეუძლია თუ არა ტურინგის ცნობადმა ენამ შექმნას გადამწყვეტი ენის ქვეჯგუფი?
- გადასაწყვეტია თუ არა ტურინგის მანქანის გაჩერების პრობლემა?
- თუ გვაქვს ორი TM, რომელიც აღწერს გადაწყვეტილ ენას, არის თუ არა ეკვივალენტობის საკითხი ჯერ კიდევ გადაუჭრელი?
- რით განსხვავდება წრფივი შეზღუდული ავტომატების მიღების პრობლემა ტურინგის მანქანებისგან?
- მოიყვანეთ პრობლემის მაგალითი, რომელიც შეიძლება გადაწყდეს წრფივი შემოსაზღვრული ავტომატით.
- განმარტეთ გადაწყვეტილების ცნება ხაზოვანი შეზღუდული ავტომატების კონტექსტში.
- როგორ მოქმედებს ფირის ზომა ხაზოვანი შეზღუდულ ავტომატებში განსხვავებული კონფიგურაციების რაოდენობაზე?
- რა არის მთავარი განსხვავება წრფივი შეზღუდულ ავტომატებსა და ტურინგის მანქანებს შორის?
იხილეთ მეტი კითხვა და პასუხი Decidability-ში