Klasifikasi Chomsky

Klasifikasi Chomsky

Teori Otomata berkaitan erat dengan teori bahasa formal. Ada beberapa hal yang berkaitan dengan Otomata, yaitu Grammar. Grammar adalah bentuk abstrak yang dapat diterima untuk membangkitkan suatu kalimat otomata berdasarkan suatu aturan tertentu. Grammar G didefinisikan sebagai pasangan 4 tupel, G (V_N, V_T, S, dan Q), dan dituliskan sebagai G (V_N, V_T, S, Q), dimana :

 

V_T             :  Himpunan  simbol-simbol  terminal  (atau  himpunan  token -token, 

                    atau alfabet)

Derivasi akan berakhir jika sentensial yang dihasilkan adalah sebuah kalimat yang tersusun atas simbol-simbol terminal. Sentesial adalah string yang tersusun atas simbol terminal atau simbol non terminal atau campuran keduanya. Yang termasuk dalam simbol terminal diantaranya :

1.   Huruf kecil anggota alfabet → kalimat → Bahasa

2.   Simbol Operator (+, -, *, ^)

3.   Simbol tanda baca (titik dan Koma, ?, !)

4.   String yang dicetak tebal, seperti if, then, dan else.   

V_N                : Himpunan simbol-simbol non terminal

Yang termasuk dalam simbol Nonterminal :

1.   Huruf Besar (kapital)

2.   Simbol Awal/Start, misal S

3.   String yang dicetak miring, seperti expr.

4.   Simbol Start (S), dimana simbol ini merupakan bagian dari simbol Nonterminal.

S Î V        : Simbol awal (atau simbol start)

Q              : Himpunan produksi

Bentuknya aàb yang artinya ruas kiri produksi (a) menurunkan ruas kanan produksi 

(b).

Dimana pada Tahun 56-59 Noam chomsky melakukan penggolongan tingkatan dalam bahasa, yaitu menjadi 4 tipe class.  Aturan produksi dinyatakan sebagai a ® b, artinya a menurunkan b  . Berdasarkan   komposisi bentuk ruas kiri dan ruas kanan produksinya (a ® b), Noam Chomsky  mengklasifikasikan 4 tipe tingkatan grammar, Penggolongan tingkatan itu disebut dengan hirarki Comsky. Adapun pembagian classnya sebagai berikut :

Grammar tipe ke-0 : Unrestricted Grammar (UG), Ciri : a, b Î (V_T½V_N)*, ïaï> 0 

Grammar tipe ke-1 : Context Sensitive Grammar (CSG), Ciri : a, b Î (V_T½V_N)*, 0 < ïaï £ ïbï 

     Grammar tipe ke-2 : Context Free Grammar (CFG), Ciri : a Î V, b Î (V_T½V_N)*
     Grammar tipe ke-3 : Regular Grammar (RG),  Ciri : a Î V, b Î {V_T, V_TV_N} atau a Î V, b Π
     {V_T, V_NV_T}

     Ciri-ciri RG sering dituliskan sebagai :  a Î V, b Î {a, bC} atau a Î V, b Î {a, Bc}

   Mesin Pengenal Bahasanya

Kelas Bahasa	Mesin Pengenal Bahasa
Unrestricted Grammar (UG)	Mesin Turing (Turing Machine), TM
Context Sensitive Grammar (CSG)	Linear Bounded Automaton, LBA
Context Free Gammar (CFG)	Automata Pushdown (Pushdown Automata), PDA
Regular Grammar, RG	Automata Hingga (Finite Automata)