HIERARKI CHOMSKY

Hierarki Chomsky  

            Hierarki Chomsky merupakan tata Bahasa (Grammar) bisa didefinisikan secara formal sebagai kumpulan dari himpunan - himpunan variable, simbol-simbol terminal, simbol awal, yang dibatasi oleh aturan - aturan produksi.Berikut adalah pengkategoriannya :

1)      Tipe 0 / Unrestricted / Natural Language

Ø  Simbol pada ruas sebelah kiri harus minimal ada sebuah symbol variable

Ø  Tidak ada batasan aturan produksinya

Example :

Abc        ->     Dc  =>  DITERIMA

ABC        ->     b    =>  DITERIMA

abc        ->     GH =>  DITOLAK

2)      Tipe 1 / Context Sensitive

Ø  Simbol pada ruas sebelah kiri harus minimal ada sebuah symbol variable

Ø  Panjang string pada ruas kiri <= panjang string pada ruas kanan

Example :

Ab          ->    Def =>  DITERIMA

ABC        ->    de  =>  DITOLAK

3)      Tipe 2 / Context Free

Ø  Simbol pada ruas sebelah kiri harus berupa sebuah symbol variable

Example :

A             ->  CDeFG =>  DITERIMA

B             ->  BcDe    =>  DITERIMA

a              ->  BC        =>  DITOLAK

AA          ->  DefG    =>  DITOLAK

4)      Tipe 3 / Regular Grammar

Ø  Simbol pada ruas sebelah kiri harus berupa sebuah symbol variable

Ø  Symbol pada sebelah kanan maksimal hanya memiliki sebuah symbol variable, dan jika ada terletak pada posisi paling kanan

Example :

A             ->  e       =>  DITERIMA

B             ->  fgh    =>  DITERIMA

C             ->  D       =>  DITERIMA

A             ->  bD    =>   DITERIMA

Ab          ->  bA    =>   DITOLAK

A             ->  aBc   =>   DITOLAK