Materi Kuliah Teori Komputasi Semsester 6 Grammar dan Tata Bahasa

 

KESIMPULAN

Grammer atau Tata Bahasa

Grammer adalah sebagi kumpulan dari himpunan himpunan variabel, simbol-simbol terminal, simbol awal, yang dibatasi oleh aturan-aturan produksi.  Aturann Produksi merupakan pusat dari Grammer yang menspesifikasikan bagaimana suatu grammer melakukan transformasi suatu string atau karakter benttuk lainya.

Semua aturan produksi dinyatakan dalam bentuk “ α-β (bisa dibaca α menghasilkan β atau dibaca α mnurunkan β).  α menurunkan simbol-simbol pada ruas kiri aturan produksi, sedangkan β merupakan simbol-simbol ruas kanan aturan produksi.

Simbol simbol tersebut dapat berupa simbol terminal (Vt) atau simbol NON-Terminal (Vn)/Variabel. Simbol Vn adalah simbol yang msih dapat diturunkan biasanya idntik dengan huruf besar (‘A’,’B’,’C’) . Simbol Vt adalah simbol yang sudah tidak dapat diturunkan lagi, biasanya identik dengan huruf kecil. (‘a’,’b’,’c’). Dengan menerapkan aturan produksi suatu grammer bisa menghasilkan sejuamlah string.

Grammar dan Klasifikasi Chomsky

Grammar G didefinisikan sebgai 4 pasangan tuple : VT , VN , S, dan Q, dan dituliskan sebagai g (VT , VN , S , Q) dimana :

VT       : himpunan simbol simbol terminal ( atau h{impunan himpunan token-token, atau alfabet).

VN      : Himpunan simbol – simbol non terminal.

S € VN : Simbol awal (atau simbol strart).

Q         : Hompuanan Produksi.

Berdasarkan komposisi bentuk ruas kiri dan ruas kanan produksinya (α ― β ), Noam Chomsky mengsalasifikasikan 4 tipe Grammar

1.      Gramar tipe ke-0 Unrestricted Grammar (UG)

Ciri : α, β , € (VT|VN)*, |α| > 0 atau |α|> |β|.

2.      Gramar tipe ke-1 : Convert Sersite Grammar (CSG)

Ciri : α , β , € (VT | VN )* , 0 < |α| ≤ |β|.

3.      Gramar tipe ke-2 Context Free Grammar (CFG)

Ciri : α € VN , β € (VT | VN)*

4.      Grammar tipe ke-3 : Reguler Grammar (RG)

Ciri : α € VN , β €  {VT , VT , VN } atau α € VN , β € {VT , VN VT}

Latihan Soal

 

1. Tentukan apakah produksi-produksi berikut memenuhi aturan grammer Reguler:

A→b(Diterima)

B→bdB(Diterima)

B→C(Diterima)

B→bC(Diterma)

B→Ad(Ditolak,karena simbol variabel pada sebelah kanan harus berada pada

posisi paling kanan)

B→bcdef (Ditenma)

A→aSa(Ditolak.karena simbol variabel pada simbol sebelah kanan simbol tidak

terletak di posisi paling kanan)

A→ aSS (Ditolak,karena simbol pada sebelah kanan maksimal hanya memilki

sebuah simbol variabel)

Ad→ dB (Ditolak, karena simbol pada sebelah kiri harus berupa simbol variabel)

2. Tentuan apakah produksi-produksi berikut memenuhi aturan grammer bebas konteks:

A→aSa(Diterima)

B→Ace(Diterima)

B→ab (Diteruma)

B→bcdef(Diterima)

B→bcdefG(Diteruma)

B→aSS(Diterima)

A→BCDEF(Diterima)

A →.AAAA(Diterima)

Ad→bB (Ditolak karena simbol pada sebelah kiri harus berupa sebuah variabel)

3. Tentukan apakahi prodaksi-prodiksi berikut memenuhi aturan grammer Unrestricted

ad → b (Ditolak, karena simbol pada sebelah kiri tidak ada sebuah simbol variabel)

abC→DE(Diterima),

AB→cde(Ditenma)

ABCDEFG →h(Diterima)

bA→CDEFG(ditenma)