Grammar Dan Bahasa dalam Teori Bahasa dan Otomata

GRAMMAR DAN BAHASA

—  Grammar adalah sebagai kumpulan dari himpunan-himpunan variabel, simbol-simbol terminal, simbol awal, yang dibatasi oleh aturan-aturan produksi.

—  Aturan produksi merupakan pusat dari grammar yang menspesifikasikan bagaimana suatu grammar melakukan transformasi suatu string atau karakter ke bentuk lainnya.

—  Semua aturan produksi dinyatakan dalam bentuk “ α à β “ (bisa dibaca α menghasilkan β, atau dibaca α  menurunkan β)

—  α merupakan simbol-simbol pada ruas kiri aturan produksi, sedangkan β merupakan simbol-simbol ruas kanan aturan produksi

—  Simbol-simbol tersebut dapat berupa simbol terminal (Vt) atau simbol NON-Terminal (Vn)/Variabel.

—  Simbol Vn adalah simbol yang masih dapat diturunkan, biasanya identik dengan huruf besar (‘A’,’B’,’C’)

—  Simbol Vt adalah simbol yang sudah tidak dapat diturunkan lagi, biasanya identik dengan huruf kecil (‘a’,’b’,’c’)

—  Dengan menerapkan aturan produksi, suatu grammar bisa menghasilkan sejumlah string.

—  Contoh aturan produksi :

E à T | T+E | T * E
T à a

Dari aturan produksi di atas, menghasilkan suatu variabel a atau variabel ekspresi a+a atau a*a

—  E à T
T à a

—  E à T+E
E à a+T
E à a+a

—  E à T*E
E à a*T
E à a*a

   Grammar G didefinisikan sebagai pasangan 4 tuple : VT , VN , S, dan Q, dan dituliskan sebagai G(V_T , V_N,   S, Q), dimana :

                V_T   : himpunan  simbol-simbol  terminal   (atau  himpunan token-token, atau alfabet)

                V_N   : himpunan simbol-simbol non terminal

                S Є V_N   : simbol awal (atau simbol start)

Q  : himpunan produksi

Berdasarkan komposisi bentuk ruas kiri dan ruas kanan produksinya (α → β), Noam Chomsky mengklasifikasikan 4 tipe grammar :

—  Grammar tipe ke-0 : Unrestricted Grammar (UG)

                Ciri : α, β Є (V_T | V_N )*, |α|> 0 atau |α|> |β|

—  Grammar tipe ke-1 : Context Sensitive Grammar (CSG)

                Ciri : α, β Є (V_T | V_N )*, 0 < |α| ≤ |β|

—  Grammar tipe ke-2 : Context Free Grammar (CFG)

                Ciri : α Є V_N , β Є (V_T | V_N )*

—  Grammar tipe ke-3 : Regular Grammar (RG)

                Ciri : α Є V_N , β Є {V_T , V_TV_N} atau α Є V_N , β Є {V_T, V_NV_T }

—  Grammar G₁  dengan Q₁  = {S → aB,      B → bB, B → b}.

—  Jawab :

  Ruas kiri semua produksinya terdiri dari sebuah V_N  maka G₁  kemungkinan tipe CFG atau RG.

                Selanjutnya karena semua ruas  kanannya terdiri dari sebuah V_T  atau string

                V_T V_N  maka G₁  adalah RG

—  Grammar G₂  dengan Q₂  = {S → Ba,      B → Bb, B → b}.

—  Jawab :

Ruas kiri semua produksinya terdiri dari sebuah V_N maka G₂  kemungkinan tipe CFG atau RG.

                Selanjutnya karena semua ruas  kanannya terdiri dari sebuah V_T  atau string

                V_NV_T  maka G₂  adalah RG

—  Grammar G₃  dengan Q₃  = {S → Ba,      B → bB, B → b}.

—  Jawab :

Ruas kiri semua produksinya terdiri dari sebuah V_N maka G₃  kemungkinan tipe CFG atau RG.

                Selanjutnya karena ruas kanannya mengandung string V_T V_N  (yaitu bB) dan juga string V_NV_T  (Ba) maka G₃  bukan RG, dengan kata lain G₃  adalah CFG

—  Grammar G₄ dengan Q₄ = {S → aAb, B → aB}.

—  Jawab :

Ruas kiri semua produksinya terdiri dari sebuah V_N  maka G₄  kemungkinan tipe CFG atau RG.

Selanjutnya karena ruas kanannya mengandung string yang panjangnya lebih dari 2 (yaitu aAb) maka G₄  bukan RG, dengan kata lain G₄  adalah CFG

—  Grammar G₅  dengan Q₅  = {S → aA,      S → aB, aAb → aBCb}.

—  Jawab :

Ruas kirinya mengandung string yang panjangnya lebih dari 1 (yaitu aAb) maka G₅ kemungkinan tipe CSG atau UG.

                Selanjutnya karena semua ruas kirinya lebih pendek atau sama dengan ruas kananya maka G₅  adalah CSG

—  Grammar G₆  dengan Q₆ = {aS → ab,  SAc → bc}.

—  Jawab :

Ruas kirinya mengandung string yang panjangnya lebih dari 1 maka G₆  kemungkinan tipe CSG atau UG.

Selanjutnya karena terdapat ruas kirinya yang lebih panjang daripada ruas kanannya (yaitu SAc) maka G₆  adalah UG

DERIVASI KALIMAT DAN PENENTUAN BAHASA

Tentukan bahasa dari masing-masing gramar berikut :

G₁ dengan Q₁   = {1. S ® aAa,  2. A ® aAa,  3. A ® b}.

Jawab :

Derivasi kalimat terpendek :      Derivasi kalimat umum :

S Þ aAa (1)                                                        S Þ aAa               (1)

   Þ aba (3)                                                            Þ aaAaa           (2)

                                                                                                     ¼

                                                                                   Þ aⁿAaⁿ            (2)

                                                                                   Þ aⁿbaⁿ            (3)

—  Dari pola kedua kalimat disimpulkan :

                L₁ (G₁  ) = { aⁿbaⁿ ½ n ³ 1}

Tentukan bahasa dari masing-masing gramar berikut :

G₂  dengan Q₂  = {1. S ® aS,  2. S ® aB,  3. B ® bC,  4. C ® aC,  5. C ® a}.

Jawab :

Derivasi kalimat terpendek :       Derivasi kalimat umum :

S Þ aB (2)                          S Þ aS                                  (1)

   Þ abC         (3)                     ¼

   Þ aba                (5)                             Þ a^n-1S                              (1)    

                                                                   Þ aⁿ B                               (2)

                                                                   Þ aⁿbC                             (3)

                                                                   Þ aⁿbaC                           (4)

                                                                    ¼

                                                                    Þ aⁿba^m-1C                     (4)

                                                                    Þ aⁿ ba^m                         (5)

Dari pola kedua kalimat disimpulkan :

L₂  (G₂ ) = { aⁿ ba^m ½ n ³ 1, m ³ 1}

Tentukan bahasa dari masing-masing gramar berikut :

G₃ dengan Q₃  = {1. S ® aSBC,  2. S ® abC,  3. bB ® bb,  4. bC ® bc,         5. CB ® BC,  6. cC ® cc}.

Jawab :

Derivasi kalimat terpendek 1:                     Derivasi kalimat terpendek 3 :

S Þ abC               (2)                                          S Þ aSBC             (1)

   Þ abc                (4)                                             Þ aaSBCBC     (1)

Derivasi kalimat terpendek 2 :                       Þ aaabCBCBC                (2)

S Þ aSBC             (1)                                             Þ aaabBCCBC                (5)

   Þ aabCBC        (2)                                             Þ aaabBCBCC                (5)

   Þ aabBCC        (5)                                             Þ aaabBBCCC                (5)

   Þ aabbCC        (3)                                             Þ aaabbBCCC                (3)

   Þ aabbcC        (4)                                             Þ aaabbbCCC                (3)

   Þ aabbcc         (6)                                             Þ aaabbbcCC (4)

                                                                                   Þ aaabbbccC (6)

                                                                                   Þ aaabbbccc  (6)

Dari pola ketiga kalimat disimpulkan : L ₃ (G₃ ) = { aⁿbⁿ cⁿ ½ n ³ 1}

—  Tentukan sebuah grammar regular untuk bahasa L₁ = { aⁿ | n ≥ 1}

Jawab :

                Q₁ (L₁ ) = {S → aS | a}
S à a atau
S à aS à aa atau
S à aS à aaS à aaa

—  Tentukan sebuah grammar bebas konteks untuk bahasa : 

                L₂ : himpunan bilangan bulat non negatif ganjil

Jawab :

                Langkah kunci : digit terakhir bilangan harus ganjil. 

                Buat dua buah himpunan bilangan terpisah : genap (G) dan ganjil (J)

                Q₂(L₂ ) = {S → J|GS|JS,  G → 0|2|4|6|8,           J → 1|3|5|7|9}

—  Tentukan sebuah gramar bebas konteks untuk bahasa :

                L₃  = himpunan semua identifier yang sah menurut bahasa pemrograman Pascal

dengan batasan : terdiri dari simbol huruf kecil dan angka, panjang identifier boleh lebih dari 8    karakter   

Jawab :

                Langkah kunci : karakter pertama identifier harus huruf. 

                Buat dua buah himpunan bilangan terpisah : huruf (H) dan angka (A)

                Q₃ (L₃ ) = {S → H|HT, T → AT|HT|H|A,   H → a|b|c|…,  A → 0|1|2|…}

—  Contoh :

—  G₁ :  V_T = {I,  Love, Miss, You}, V = {S,A,B,C}, P = {S ® ABC, A® I, B® Love | Miss, C® You}

—  S Þ ABC

—     Þ I loveYou

—  L(G₁)={I love You, I Miss You}

—   

GRAMMAR DAN KLASIFIKASI CHOMSKY LANJUT.

—  Grammar G didefinisikan sebagai pasangan 4 tuple : V_T , V_N , S, dan Q, dan dituliskan sebagai G(V_T , V_N , S, Q), dimana :

—  V_T           : himpunan  simbol-simbol  terminal  (atau  himpunan  token -token, atau alfabet)

—  V_N : himpunan simbol-simbol non terminal

—  S Î V_N  : simbol awal (atau simbol start)

—  Q             : himpunan produksi

Sampai disini dulu ya teman teman,semoga bermanfaat ...

Sumber: PPT Teori Bahasa dan Otomata  Bu Dine