უკონტექსტო გრამატიკა

უკონტექსტო გრამატიკა

არსებობს რამდენიმე სახის ავტომატი, როგორიც არის დეტერმინისტული-სასრული ავტომატი(DFA) და ასევე არადეტერმინისტული-სასრული-ავტომატი(NFA) ასევე არსებობს რეგულარული-გამოსახულება(Regular-Expression). არსებობს ენები რომლებიც შესაძლებელია გამოისახოს ზემოაღნიშნული ავტომატების საშუალებით მაგრამ არსებობს ენები რომლებიც არ გამოისახებიან სასრული ავტომატებით. მაგალითად შემდეგი ენა {$0^{n}1^{n}|n>0$}. ეს ენა არის არარეგულარული ამიტომ ის ვერ გამოისახება სასრული ავტომატების საშუალებით. ასეთი ენების გამოსახატავად შემოდის ე.წ Context-Free-Grammar(CFG). CFG-ის საშუალებით შეგვიძლია ჩავწეროთ ისეთი ენებიც რომლებიც შეიცავენ რეკუსრიულ სტუქტურას. CFG-ის ზოგადი მონახაზი არის შემდეგი:

1. გააჩნია სიმრავლე, ცვლადის ჩანაცვლების წესების
2. ყოველ წესში არის ცვლადი რომელიც გადადის ისევ ცვლადში, სიტყვასა და ცვლადში ან მხოლოდ სიტყვაში
3. აუცილებლად უნდა ჰქონდეს საწყისი ცვლადი საიდანაც ვიწყებთ სიტყვის დაგენერირებას.
4. ყოველი წესი ჩაწერილია ერთი ხაზით.

უკონტექსტო გრამატიკის აგება

როგორ უნდა ავაგოთ CFG კონკრეტული ენისთვის. ვიწყებთ საწყისიცვლადით და ვადგენთ კონკრეტულ წესებს, რომლის მეშვეობითაც მივიღებთ ჩვენს მიერ დასახელებულ ენას ან კონკრეტულ სიტყვას. განვიხილოთ CFG მაგალითი. მაგალითად ავიღოთ შემდეგი ენა {$0^{n}1^{n}|n>0$} და შევეცადოთ ჩავწეროთ CFG-ის გამოყენებით. CFG-ის აღიწერება შემდეგნაირად:

1. S -> 0A1
2. A -> 0A1
3. A -> “”

აღწერილი CFG იმოქმედებს შემდეგნაირად. აიღებს S საწყის ცვლადს რომელიც გადავა 0A1-ში. ამის შემდეგ 0A1 გადავა 2 წესის მიხედვით 00A11-ში ან 3 წესის მიხედვით 01-ში. პროცესის დასრულებას უზრუნველყოფს მესამე წესი, რისი შესრულების დროსაც პროცესი კვდება, რადგან A არ გადადის რაიმე ცვლადში ის მთლიანად გადაიქცევა სიტყვად. აქედან გამომდინარე ჩვენს მიერ ჩაწერილი CFG დააგენერირებს შემდეგ სიტყვებს {01, 0011, 000111, .... , 0n1n,....} ამ სიმრავლის ნებისმიერ სიტყვას. თუ ჩვენს მიერ დაწერის CFG-ის დავარქმევთ C-ს. მაშინ C-ს ენის ფორმალური ჩანაწერი იქნება შემდეგი L(C)={$0^{n}1^{n}|n>0$}.

უკონტექსო გრამატიკის წესები

Context free Grammar ჩაიწერება შემდეგნაირად CFG = {V,E,R,S} სადაც:

1. V არის ცვლადების სასრული სიმრავლე.
2. E არის სტრინგის ქარაქტერები, ე.წ ლიტერალები
3. R არის სასრული სიმრავლე წესების, სადაც ცვლადი გადადის ცვლადსა და ლიტერალში.
4. S არის საწყისი ცვლადი S ეკუთვნის V-s.

განვიხილოთ შემდეგი მაგალითი.

1. S -> aSa | b

ვაჩვენოთ თუ როგორ ენას აგენერირებს ჩვენს მიერ დაწერილი CFG. e არის ასევე ცარიელი სიტყვა. როგორც ხედავთ S შეიძლება გადავიდეს aSa -> aaSaa -> aaaSaaa -> aaabaaa. ჩვენი შექმნილი CFG-ის ენას წარმოადგენს L(G)={ $a^{n}ba^{n}|n>=0$}.

თავისუფალი გრამატიკის თვისებები

დავუშვათ გვინდა ორი ენის გაერთიანება მაგალითად {$a^{n}ba^{n}|n>=0$} U { $b^{m}ab^{m}|m>=0$} ასეთ შემთხვევაში გვინდა ორი CFG-ის გაერთიანება რაც შეგვიძლია გავაკეთოთ შემდეგნაირად. საწყისი ცვლადი გადავიყვანოთ ან პირველი ენის საწყის ცვლადში ან მეორეენის საწყის ცვლადში. ამის შემდეგ ან ერთ ენას მივიღებთ ან მეორეს.

1. S - > A | B
2. A -> aAa | b
3. B -> bBb | a

ამ მაგალითში CFG-ის ხე იყოფა 2 ნაწილად თითოეული ნაწილი აგენერირებს სხვადასხვა ენას. სიტყვების მიღების ხე არის შემდეგნაირი.




           S
           |
          / \
         A - B
        /     \
       / \    / \
     aAa  b  a  bBb
     /             \
    / \           / \
 aaAaa b         a bbBbb

როგორც ნახაზზე ჩანს ხის მარცხენა მხარე აგენერირებს ენას {$a^{n}ba^{n}|n>=0$} ხოლო მარჯვენა მხარე {$b^{m}ab^{m}|m>=0$}. ამიტომ CFG-ის ენა იქნება L(G)={$a^{n}ba^{n}|n>=0$} U {$b^{m}ab^{m}|m>=0$}. ანუ ორი CFG ის გაერთიანება არის ისევ CFG. რაც შეეხება კონკეტენაციას თუ გვინდა ახალი CFG ის ენა იყოს გაერთიანების ნაცვლად კონკატენაცია ანუ L(G)= {$a^{n}ba^{n}b^{m}ab^{m}|n,m>0$}. ამ ენის CFG ძალიან ჰგავს წინათ დაწერილ CFG-ის წესებს. მხოლოდ კეთდება ერთი ცვლილება. წინა შემთხვევაში გვინდოდა რომელიმე ერთი ენის არჩევა და შემდეგ ამ ენის სტრინგის დაგენერირება. ამ შემთხვევაში გვინდა ორივე სტრინგის დაგენერირება რომლებიც ერთმანეთის გვერდით დგანან. ანუ უნდა ავიღოთ პირველი ენის სტრინგი და მეორე ენის სტრინგ და შევაწებოთ. რაც ხდება კიდეც ქვემოთ დაწერილ წესებში.

1. S -> AB
2. A -> aAa | b
3. B -> bBb | a

ეს CFG დააგენერირებს ცალ-ცალკე 2 ენის სტრინგს A და B ცვლადის გამოყენებით. ხოლო შეერთება ამ სტრინგების ხდება პირველი წესის დახმარებით როდესაც S გადადის AB-ში. A და B მიიღებენ ცალ-ცალკე სიტყვებს რომლებიც შეერთებული იქნებიან.ანუ ორი CFG-ის კონკატენაცია არის ისევ CFG
S -> AB -> aAabBb -> aaAaabbb -> aaaaaabbb ამ სისტემით მივიღებთ ამ სიტყვას.

უკონტექსტო გრამატიკის სიმძლავრე

კითხვა არის შემდეგი, ნუთუ არსებობს ისეთი ენა რომელსაც ვერ მივიღებთ CFG-ის საშუალებით? ასეთი ენა არსებობს მაგალითად {$0^{n}1^{n}0^{n}1^{n}|n>0$}. იმის გასარკვევად არსებობს თუ არა რაიმე CFG რომელიც დააგენერირებს კონკრეტულ ენას, არსებობს 2 გზა. ან უნდა ავაგოთ PDA(push down automata) თუ არსებობს რაღაც ენისთვის PDA, მაშინ არსებობს ასევე შესაბამისი CFG. მეორე ვარიანტი, დავამტკიცოთ რომ არ შეიძლება არსებობდეს CFG ამ ენისთვის CFG Pumping Lema-ის გამოყენებით.