HIRARKI CHOMSKY

Teori Otomata berkaitan erat dgn teori bahasa formal.
Ada beberapa hal yang berkaitan dengan Otomata, yaitu Grammar. Grammar adalah bentuk abstrak yang dapat diterima (accept) untuk membangkitkan suatu kalimat otomata berdasarkan suatu aturan tertentu.

Grammar G didefinisikan sebagai pasangan 4 tuple, G(Vt , Vn , S, P) :

1. Himpunan Simbol Terminal (Vt).

    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.   

2.  Himpunan simbol Nonterminal (Vn)

     Yang termasuk dalam simbol Nonterminal :

1. Huruf Besar (kapital)
2. Simbol Awal/Start, misal S
3. String yang dicetak miring, seperti expr.

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

4. Himpunan Produksi (P)

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

Tahun 1959 seorang ahli bernama Noam Chomsky melakukan penggolongan tingkatan bahasa menjadi empat tipe, yaitu :

Keterangan Symbol :
* disebut juga cleene closure
 | disebut juga alternate