HIRARKI CHOMSKY

                    Tata Bahasa (Grammar) bisa di definisikan secara formal sebagai kumpulan dari himpunan - himpunan variable, simbol-simbol terminal, simbol awal, yang dibatasi oleh aturan - aturan produksi. Pada tahun 1959 seorang ahli bernama Noam Chomsky melakukan penggolongan tingkatan bahasa menjadi , yang disebut dengan Hirarky Chomsky, Penggolongan tersebut bisa dilihat pada tabel berikut :

Bahasa	Mesin Otomata	Batasan aturan produksi
Regular/ tipe 3	Finite state Automata (FSA) meliputi Deterministic Finite Automata (DFA) & Non-Deterministic finite Automata (NFA)	α adalah sebuah simbol variable β maksimal memiliki sebuah simbol variabel yang bila ada terletak  diposisi paling kanan
Bebas konteks/ Context free/tipe 2	Push Down Automata (PDA)	α adalah sebuah simbol variabel
Context Sensitive/Tipe1	Linier Bounded Automata	|α| ≤ |β|
Unrestricted/ Phasw Structure/ Natural Language/ Tipe 0	Mesin Turing	Tidak ada batasan

           Kita bisa melihat penggolongan diatas berdasarkan pembatasan yang dilakukan pada aturan produksinya. Aturan produksi merupakan pusat dari tata bahasa, yang menspesifikaasikan bagaimana suatu tata bahasa melakukan transformasi suatu string ke bentuk lainnya, dan melalui aturan produksi tersebut di definisikan suatu bahasa yang berhubungan dengan tata bahasa tersebut. Disini semua aturan produksinya dinyatakan dalam bentuk "α→β" (bisa dibaca : α menghasilkan β, atau dibaca α menurunkan β), dimana α menyatakan simbol-simbol pada ruas kiri aturan produksi (sebelah kiri tanda "→") dan β menyatakan simbol-simbol pada ruas kanan aturan produksi (sebelah kanan tanda "→" dan bisa juga disebut sebagai hasil produksi ). Simbol-simbol tersebut bisa berupa simbol terminal atau simbol nonterminal/variabel. simbol variabel/nonterminal adalah simbol yang masih bisa diturunkan, sedangkan simbol terminal sudah tidak bisa diturunkan lagi. Simbol terminal biasanya dinyatakan dalam huruf kecil, misal 'a','b','c'. Simbol nonterminal/variabel biasanya dinyatakan huruf besar, misal 'A','B','C'.

           Dengan menerapkan aturan produksi, suatu tata bahasa bisa menghasilkan sejumlah string. Himpunan semua string tersebut adalah bahasa yang didefinisikan oleh tata bahasa tersebut.

Contoh aturan produksi :

T→a

bisa dibaca "T menghasilkan a"

E→T | T+E

bisa dibaca "E menghasilkan T atau E menghasilkan T+E"

            Simbol '|' menyatakan 'atau', biasa digunakan untuk mempersingkat penulisan aturan produksi yang mempunyai ruas kiri yang sama pada contoh diatas:

E→T | T+E

merupakan pemendekan dari aturan produksi :

E→T

E→T+E

            

             Bahasa manusia/bahasa alami termasuk kedalam grammar (tata bahasa) Tipe 0/Unrestricted, dimana tidak ada batasan pada aturan produksinya. Misalkan saja :

Abc→De

             Pada bahasa Context Sensitive, panjang string pada ruas kiri  ≤ panjang ruas kanan 

(|α| ≤ |β|). Contoh aturan produksi yang context sensitive :

Ab→DeF

CD→eF

Perhatikan aturan produksi seperti dibawah  ini :

S→e

Kita ketahui |S| =1, sedang |Ɛ|=0, menurut aturan context sensitive aturan produksinya itu tidak diperkenankan, tetapi disini kita buat suatu perkecualian sehingga S→Ɛ dianggap memenuhi context sensitive grammar.

             Batasan context sensitive biasanya turut digunakan dalam proses analisis semantik pada tahapan kompilasi.

             Pada bahasa bebas konteks, batasanya bertambah lagi dengan ruas kiri haruslah tepat satu simbol variabel. Misalnya :

B→CDeFg

D→BcDe

             Bahasa bebas konteks menjadi dasar dalam pembentukan suatu parser/proses analisis sintaksis. Bagian sintaks dalam suatu kompilator kebanyakan di definisikan dalam tata bahasa bebas konteks (context free grammar), yang dideskripsikan secara formal dengan notasi BNF (backup Naur Form atau Backup Normal Form).

             Pada bahasa regular batasanya bertamabah dengan ruas sebelah kanan maksimal memiliki sebuah simbol variabel yang terletak dipaling kana. Artinya bisa memiliki simbol terminal saja dalam jumlah tidak dibatasi, tetapi bila terdapat simbol variabel, maka simbol variabel tersebut hanya berjumlah 1 (satu ) dan terletak diposisi paling kanan. Misalnya :

A→e

A→efg

A→efgH

C→D  

 

 Bisa kita lihat, batasannya makin bertambah dari Tipe 0 ke Tipe 3. Berdasarkan keterkaitan antar Tipe bahasa tersebut, Bisa pula dilihat secara sederhana pada gambar diatas.

Catatan : Perhatikan bahwa :                 Aturan produksi seperti Ɛ → Abd Bukan aturan produksi yang legal, karena simbol Ɛ tidak boleh berada pada ruas kiri. Aturan produksi yang ruas kirinya hanya memuat simbol terminal saja, Seperti : a → bd ab → bd bukan aturan produksi yang legal (untuk unrestricted grammar sekalipun), karena ruas kiri harus memuat simbol yang bisa diturunkan, sementara contoh diatas ruas kiri hanya terdiri dari simbol terminal saja padahal sesuai definisinya simbol terminal sudah tidak bisa diturunkan lagi, berbeda dengan aturan produksinya.