HIRARKI CHOMSKY

Ada 4(empat) kelas pengelompokan suatu bahasa, yang kita kenal dengan “Chomsky Hierarchy”. Hirarki atau tingkatan bahasa ini dikembangkan oleh Noam Chomsky pada tahun 1959.

Pengelompokan bahasa menurut Chomsky

 

1.    Tata Bahasa Regular (Regular Grammar)/Tipe 3

a ® b

dimana :

a adalah simbol nonterminal tunggal

          b maksimal memiliki maksimal satu simbol non terminal tunggal dan ditempatkan pada posisi paling kanan.

Mesin pengenal bahasa disebut : Finite State Automata (FSA)

   Contoh :

            G = (V, T, P, S)

                   V = {S, A, B}

                               T = {0, 1}

                               P : S ® 0A | 1B | 0

                                    A ® 0A | 0S | 1B

                         B ® 1B | 1 | 0 | e

        

2.    Tata Bahasa Bebas Konteks (Conteks Free Grammar)/Tipe 2

a ® b

dimana :

a adalah simbol nonterminal tunggal

Mesin pengenal bahasa disebut : Push Down Automata (PDA)

   Contoh :

            G = {V, T, P, S}

       V = {S, A, B}

                   T = {a, b}

                   P : S ® aB | bA

                       A ® a | aS | bAA

                        B ® b | bS | aBB

3.    Tata Bahasa Sensitive Konteks (Conteks Sensitive Grammar)/Tipe 1

a ® b

dimana :

                        |a| £ |b|

Mesin pengenal bahasa disebut : Linear Bounded Automata (LBA)

    Contoh :

            G = {V, T, P, S}

                   V = {S, B, C}

                   T = {a, b, c}

                

       P : S ® aSBC | aBC | e

                          CB ® BC

                          aB ® ab

                          bB ® bb

                          bC ® bc

                          cC ® cc

       keterangan

            S ® e, karena S adalah simbol awal, maka ini juga memenuhi

                        Walau panjang S = 1 dan panjang e = 0

4.    Tata Bahasa Tanpa Batas (Unrestricted Grammar)/Tipe 0

Tidak ada batasan

                   

Mesin pengenal bahasa disebut : Mesin Turing

           

    Contoh :

                  G = (V, T, P, S)

                         V = {S, A, B, G}

                         T = {a, b,d}

                         P : S ® aSa

                             A ® bdG

                             AB ® a

Suatu bahasa dikatakan tipe i (Li), jika dihasilkan untuk tata bahasa tersebut tipe i :

                        L₃ Ì L₂ Ì L₁ Ì L₀

Kata Kosong

Definisi sebelumnya pada Regular Grammar, Context Free Grammar dan Context Sensitive Grammar, tidak terdapat suatu kata kosong (l), maka definisi untuk tata bahasa di atas perlu diperluas sehingga terdapat definisi S ® l.

Teorema

Jika Bahasa (L) merupakan Regular Grammar, Context Free Grammar dan Context Sensitive Grammar maka terdapat L È {l} yang merupakan Regular Grammar, Context Free Grammar dan Context Sensitive Grammar.

Contoh

Grammar (G) = (V, T, P, S), yang merupakan tipe 1 hirarki Chomsky

Dimana

            V = {S, B, C}

            T = {a, b, c}

            P : S    ® aSBC | aBC

                 CB ® BC

                 aB ® ab

                 bB ® bb

                 bC ® bc

                 cC ® cc

Maka akan didapat :

            S Þ aBC Þ abC Þ abc

            S Þ aSBC Þ aaBCBC Þ  aaBBCC Þ aabBCC Þ aabbCC Þ aabbcC Þ aabbcc

Dari proses di atas terdapat bahasanya yaitu :

            L(G) = {w | w Î aⁿ bⁿ cⁿ, n ³ 1}

 

Tata Bahasa Rekursif

Tata bahasa disebut “Rekursif” jika terdapat sebuah algoritma yang dapat menentukan untuk setiap string w menghaislkan tata bahasa (G).

Teorema

Jika G = (V, T, P, S) merupakan context sensitive grammar yang memiliki G rekursif, maka G rekursif itu berlaku juga untuk regular grammar dan context free grammar.

 

Bukti

Misal diasumsikan bahwa aturan produksi P tidak berisi S ® l dan string w Î V_T* dengan panjang string sebesar n. Kita mendefinisikan bahwa T_m sebagai sekumpulan kata a dalam V₊ dengan panjang maksimal string n. Sehingga didapatkan suatu hasil turunan dengan langkah maksimal dilakukan adalah m langkah.

Jika T₀ merupakan langkah awal, maka langkah awal berisikan simbol awal dari aturan produksi. Apabila S merupakan simbol awal maka T₀ = {S}. Dengan mudah kita dapat menetukan T_m dapat diperoleh dari T_m-1. Apabila kita mengetahui bahwa panjang kata £ n, maka dapat diturunkan dari kata-kata T_m-1 yang merupakan sebuah aplikasi prosuksi.

Pendefinisan Formal

T_m = T_m-1 È {a | untuk b dalam T_m-1, dimana b ® a dan |a| £ n} dan juga, jika S Þ* a, dan |a|  £ n, maka a terdapat dalam T_m untuk m tertentu. Jika S tidak menurunkan a atau |a| > n, maka a tidak terdapat dalam T_m untuk semua nilai m.

Kita akan membuat algoritma untuk menentukan T₁, T₂, T₃, … sehingga diperoleh m dimana T_m = T_m-1. Jika string w terdapat dalam T_m, maka string w terdapat dalam L(G), karena untuk j > m, dimana T_j = T_m di sini jelas bahwa jika string w dalam Tm, didapat S Þ_G*w.

Contoh

            1. Misal S  Þ  aBC Þ abC Þ abc

                Maka :

                        T₀ = {S}

                        T₁ = {S, aBC}

                        T₂ = {S, aBC, abC}

                        T₃ = {S, aBC, abC, abc}

2.    Diketahui G = (V, T, P, S)

Dimana :

                  V = {S, B, C}

                  T = {a, b, c}

                  P : S ® aSBC | aBC

                       aB ® ab

                       CB ® BC 

                        bB ® bb

                        bC ® bc

                        cC ® cc

Tentukan apakah string w = abac diterima oleh tata bahasa di atas?

Jawab

(a). Kemungkinan Pertama

T₀ = {S}

T₁ = {S, aSBC}

T₂ = {S, aSBC, aaBC}

T₃ = {S, aSBC, aaBC, aabC}

T₄ = {S, aSBC, aaBC, aabC, aabc}

Hasil kemungkinan pertama bahwa w = abac Ï L(G)

(b). Kemungkinan Kedua

T₀ = {S}

T₁ = {S, aBC}

T₂ = {S, aBC, abC}

T3 = {S, aBC, abC, abc}

Hasil kemungkinan kedua bahwa w = abac Ï L(G)

Jadi dapat kita buat suatu kesimpulan bahwa string w = abac Ï L(G), dimana hasil kemungkinan pertama adalah “aabc” dan hasil kemungkinan kedua adalah “abc”, sementara string w yang diinginkan adalah “abac”