Pertemuan 2 TBO
2. Hirarki Chomsky
Secara umum tata bahasa dirumuskan sebagai berikut :
- ɑ→β, yang berarti ɑ menghasilkan β atau ɑ menurunkan β. Di mana ɑ menyatakan simbol-simbol pada ruas kiri aturan produksi (sebelah kiri tanda "→") dan β menyatakan simbol-simbol pada ruas kanan aturan produksi (sebelah kanan tanda "→")
- Simbol variabel / non terminal adalah simbol yang masih bisa diturunkan dan ditandai dengan huruf besar seperti A, B, C, dan seterusnya.
- Simbol terminal adalah simbol yang sudah tidak bisa diturunkan dan ditandai dengan huruf kecil seperti a, b, c, dan seterusnya.
A. Tipe 0 / Unrestricted / Natural Language
Aturan :
- Simbol pada ruas sebelah kiri harus harus minimal ada sebuah simbol variabel
- Tidak ada batasan pada aturan produksinya
Misal :
- Abc→De (diterima)
- ABc→b (diterima)
- abc→GHI (ditolak, karena simbol pada ruas sebelah kiri tidak ada simbol variabel)
B. Tipe 1 / Conteks Sensitive
Aturan :
- Simbol pada ruas sebelah kiri harus minimal ada sebuah simbol variabel
- Panjang string pada ruas kiri ≤ panjang string pada ruas kanan |ɑ| ≤ |β|.
Misal :
- Ab→DeF (diterima)
- CD→eF (diterima)
- ABC→DE (ditolak, karena jumlah simbol pada ruas sebelah kiri lebih banyak dari sebelah kanan)
C. Tipe 2 / Bebas Konteks / Context Free
Aturan :
- Simbol pada sebelah kiri harus berupa sebuah simbol variabel
Misal :
- B→CDeFG (diterima)
- D→BcDe (diterima)
- a→b (ditolak, karena simbol pada ruas sebelah kiri bukan simbol variabel melainkan simbol terminal)
D. Tipe 3 / Regular Aturan
Aturan :
- Simbol pada sebelah kiri harus berupa sebuah simbol variabel
- Simbol pada sebelah kanan maksimal hanya memiliki sebuah simbol variabel dan bila ada, terletak di posisi paling kanan.
Misal :
- A→e (diterima)
- A→fgh (diterima)
- A→eH (diterima)
- C→D (diterima)
- A→He (ditolak, karena simbol variabel pada ruas sebelah kanan harus terletak pada posisi paling kanan sedangkan itu terletak di posisi kiri)
Komentar
Posting Komentar