LATIHAN BAB I 1. Tentukan apakah produksi-produksi berikut memenuhi aturan tata bahasa Reguler : Penyelesaian : Bahasa Reguler mempunyai batasan yaitu panjang ruas kiri ≤ panjang ruas kanan, ruas kiri haruslah tepat satu simbol variabel, ruas kanan maksimal memiliki sebuah simbol variabel yang terletak di paling kanan. a] A b, merupakan bahasa reguler b] B bdB, merupakan bahasa reguler c] B C, merupakan bahasa reguler d] B bC, merupakan bahasa reguler e] B Ad, bukan bahasa reguler karena memiliki simbol variabel yang tidak terletak di paling kanan. f] B bcdef, merupakan bahasa reguler g] B bcdefG, merupakan bahasa reguler karena ruas kanan memiliki sebuah simbol variabel yang terletak di paling kanan. h] A aSa, bukan bahasa reguler karena memiliki simbol variabel yang tidak terletak di paling kanan. i] A aSS, bukan bahasa reguler karena memiliki 2 simbol variabel. j] A ɛ, merupakan bahasa reguler k] Ad dB, bukan bahasa reguler karena ruas kiri memiliki 2 simbol. 2. Tentukan apakah aturan produksi-produksi berikut memenuhi aturan tata bahasa bebas konteks: Bahasa bebas konteks mempunyai batasan yaitu panjang ruas kiri ≤ panjang ruas kanan, ruas kiri haruslah tepat satu simbol variabel. a] A aSa, merupakan bahasa bebas konteks b] A Ace, merupakan bahasa bebas konteks c] A ab, merupakan bahasa bebas konteks d] A ɛ, merupakan bahasa bebas konteks e] B bcdef, merupakan bahasa bebas konteks f] B bcdefG, merupakan bahasa bebas konteks g] A aSa, merupakan bahasa bebas konteks h] A aSS, merupakan bahasa bebas konteks i] A BCDEF, merupakan bahasa bebas konteks. j] Ad dB, merupakan bahasa bebas konteks. k] A AAAAA, merupakan bahasa bebas konteks. l] d A, bukan merupakan bahasa bebas konteks karena ruas kiri tidak mempunyai simbol variabel. 3. Tentukan apakah produksi-produksi berikut memenuhi aturan tata bahasa context sensitive : Batasan pada bahasa context sensitive yaitu, panjang string pada ruas kiri [α] lebih kecil atau sama dengan ruas kanan [β]. a] B bcdefG, merupakan bahasa context sensitive b] A aSa, merupakan bahasa context sensitive c] A aSS, merupakan bahasa context sensitive d] A BCDEF, merupakan bahasa context sensitive e] Ad dB, merupakan bahasa context sensitive f] A ɛ, merupakan bahasa context sensitive g] AB ɛ, bukan merupakan bahasa context sensitive h] ad b, bukan merupakan bahasa context sensitive i] ad ɛ, bukan merupakan bahasa context sensitive j] adC DE, bukan merupakan bahasa context sensitive k] abcDef ghijkl, merupakan bahasa context sensitive l] AB cde, merupakan bahasa context sensitive m] AAA BBB, merupakan bahasa context sensitive 4. Tentukan apakah produksi-produksi berikut memenuhi aturan tata bahasa unrestricted: a] A ɛ, merupakan bahasa unrestricted b] AB ɛ, merupakan bahasa unrestricted c] Ad b, merupakan bahasa unrestricted d] ad ɛ, bukan merupakan bahasa unrestricted e] abC DE, merupakan bahasa unrestricted f] AB cde, merupakan bahasa unrestricted g] ɛ a, bukan merupakan bahasa unrestricted h] ABCDEFG h, merupakan bahasa unrestricted i] bA CDEFGh, merupakan bahasa unrestricted LATIHAN BAB IV 1. Buatlah NFA tanpa ɛ-move yang ekivalen dengan NFA ɛ-move pada gambar dibawah ini. [Σ= [0,1,2] 0 q0 1 ɛ q1 2 ɛ q2 Penyelesaian : a. Buat tabel transisi δ q0 q1 q2 0 {q0} Ǿ Ǿ 1 Ǿ {q1} Ǿ 2 Ǿ Ǿ {q2} b. Tentukan ɛ-closure ε-cl[q0] = [q0,q1,q2] ε-cl[q1] = [q1,q2] ε-cl[q2] = [q2] c. Cari fungsi transisi Mencari [δ’] dengan rumus : δ[state,input] = ε-cl[δ[ε-cl[state],input]] δ’[q0,0]= ε-cl[δ[ε-lc[q0],0]] = ε-cl[δ[ε-lc[q0,q1,q2],0]] = ε-cl[q0] = { q0,q1,q2} δ’[q0,1]= ε-cl[δ[ε-lc[q0],1]] = ε-cl[δ[ε-lc[q0,q1,q2],1]] = ε-cl[q1] = { q1,q2} δ’[q0,2]= ε-cl[δ[ε-lc[q0],2]] = ε-cl[δ[ε-lc[q0,q1,q2],2]] = ε-cl[q2] = { q2} δ’[q1,0]= ε-cl[δ[ε-lc[q1],0]] = ε-cl[δ[ε-lc[q1,q2],0]] = ε-cl[Ǿ] ={Ǿ} δ’[q1,1]= ε-cl[δ[ε-lc[q1],1]] = ε-cl[δ[ε-lc[q1,q2],1]] = ε-cl[q1] = { q1,q2 } δ’[q1,2]= ε-cl[δ[ε-lc[q1],2]] = ε-cl[δ[ε-lc[q1,q2],2]] = ε-cl[q2] = { q2} δ’[q2,0]= ε-cl[δ[ε-lc[q2],0]] = ε-cl[δ[ε-lc[q2],0]] = ε-cl[Ǿ] ={Ǿ} δ’[q2,1]= ε-cl[δ[ε-lc[q2],1]] = ε-cl[δ[ε-lc[q2],1]] = ε-cl[Ǿ] ={Ǿ} δ’[q2,2]= ε-cl[δ[ε-lc[q2],2]] = ε-cl[δ[ε-lc[q2],2]] = ε-cl[q2] = { q2} d. Buat tabel transisi dari langkah c Tabel transisi untuk NFA tanpa ε-move δ 0 1 q0 { q0,q1,q2} {q1,q2} q1 Ǿ { q1,q2 } q2 Ǿ Ǿ 2 { q2} {q2} {q2} e. Himpunan akhir state akhir semula adalah q2, lihat ɛ-closure ε-cl[q0] = [q0,q1,q2] ε-cl[q1] = [q1,q2] ε-cl[q2] = [q2] maka, himpunan state akhir sekarang adalah {q1,q2,q2} 1 0 2 1,2 0 q1 q0 q2 0 Gambar NFA tanpa ɛ-move yang ekivalen dengan NFA ɛ-move 2. Buatlah NFA tanpa ɛ-move yang ekivalen dengan NFA ɛ-move pada gambar dibawah ini. [Σ= [0,1] 0 q0 ɛ 1 q1 3. Bila diketahui L[M1] adalah......... a. Mesin M3 yang menerima bahasa L[M3] = L[M1] + L[M2] Langkah-langkahnya adalah Tambahkan state awal untuk M3 hubungkan dengan state awal M1 dan state awal M2 menggunakan transisi ɛ Tambahkan state akhir untuk M3 hubungkan dengan state-state akhir M1 dan state-state akhir M2 menggunakan transisi ɛ 0 q0 1 q1 ɛ ɛ 0,1 ɛ qs qf 0 ɛ ɛ 0 1 q0 q1 q0 1 1 0 b. Mesin M4 yang menerima bahasa L[M4] = L[M1]L[M2] Langkah-langkahnya adalah State awal M1 menjadi state awal M4 State-state akhir M2 menjadi state akhir M4 Hubungkan state-state akhir M1 dengan state awal M2 menggunakan transisi ɛ 0 0 q0 0 1 q1 ɛ q0 1 1 1 0,1 q1 q0
0
Halo teman teman semua, pada artikel ini kita akan membahas mengenai Tata Bahasa, bagaimana itu Hirarki Chomsky dan apa itu Aturan Produksi serta bagaimana aturan yang digunakan pada setiap tipe hirarki chomsky.
Simbol terminal dan non terminal
Apa itu simbol terminal?
- simbol terminal adalah simbol yang tidak dapat diturunkan lagi
- arti bisa diturunkan yaitu misalkan simbol A yang dapat diturunkan menjadi bc
yang termasuk simbol terminal:
- huruf kecil alfabet: a,b,c
- simbol operator: + [tambah], – [kurang]
- simbol tanda baca: , [koma] ! [tanda seru]
- string yang tercetak tebal, misalnya: if, then dan else
Apa itu simbol NON terminal [Variabel]?
- adalah simbol yang masih bisa diturunkan menjadi simbol terminal atau non terminal lainnya
yang termasuk simbol NON terminal [variabel]:
- huruf besar alfabet: A, B, C
- huruf S sebagai simbol awal
- String yang tercetak miring misal expr dan stmt
Aturan Produksi
Dalam teori bahasa dan otomata, aturan produksi dinyatakan dalam:
α → β
[dibaca: alpha menghasilkan atau menurunkan beta]
- Dengan menerapkan aturan produksi, suatu tata bahasa bisa menghasilkan sejumlah string.
- Himpunan semua string tersebut adalah bahasa yang didefinisikan oleh tata bahasa tersebut.
contoh aturan produksi:
T → a
[dibaca: T menghasilkan a]
Contoh lain:
E → T | T + E
[dibaca: E menghasilkan T atau E menghasilkan T + E]
Hirarki Chomsky
Grammar
- Grammar atau tata bahasa didefinisikan secara formal sebagai kumpulan dari himpunan himpunan variabel, simbol simbol terminal, simbol awal, yang dibatasi oleh aturan aturan produksi.
4 tingkatan tata bahasa menurut Chomsky:
- Tipe 0 – Unrestricted Grammar
- Tipe 1 – Context Sensitive Grammar
- Tipe 2 – Context Free Grammar
- Tipe 3 – Regular Grammar
Tipe 0 – Unrestricted Grammar
- Aturan produksinya tidak memiliki batasan
- Dalam aturan α → β pada tipe 0:
- alpha adalah string terminal dan non-terminal dengan setidaknya 1 non-terminal
- alpha tidak boleh kosong
- beta adalah rangkaian simbol terminal dan non – terminal
- α adalah [V + T]*V[V+T]*
- β adalah [V+T]*
- note:
- [tanda plus ‘+’ dibaca atau]
- [tanda * [asterisk] yang berarti bisa tidak muncul atau bisa juga muncul hingga berkali kali [0 – n]]
- Tipe ini menghasilkan bahasa yang dikenali oleh mesin Turing
- Bahasa ini juga dikenal dengan nama “Recursively Enumerable Languages”.
jadi aturan yang perlu diingat adalah:
- α adalah [V + T]*V[V+T]*
- β adalah [V+T]*
Contoh penerapan aturan tipe 0:
- S → ACaB [Terpenuhi, karena di ruas kiri ada non terminal, di ruas kanan ada terminal dan non-terminal]
- Bc → acB [Terpenuhi, karena di ruas kiri ada non terminal, di ruas kanan ada terminal dan non-terminal]
- CB → DB [Terpenuhi]
- aD → Db [Terpenuhi]
- Sab → ba [Terpenuhi]
- A → S [Terpenuhi]
Tipe 1 – Context Sensitive Grammar
- Aturan produksinya sama dengan tipe 0 namun dibatasi dengan aturan |a|≤|b| [jumlah simbol di ruas kiri harus lebih kecil atau sama dengan jumlah simbol di ruas kanan]
- Aturan S → Ɛ dibolehkan jika S tidak muncul pada ruas kanan setiap aturan
- Menghasilkan bahasa yang dikenali oleh Linear Bound Automata
jadi aturan yang perlu diingat adalah:
- |a|≤|b|
- a adalah [V+T]*V[V+T]*
- b adalah [V+T]* [V+T] [V+T]*
Contoh penerapan:
- S → AB [Terpenuhi]
- AB → abcd [Terpenuhi, ukuran ruas kiri lebih kecil dari ruas kanan]
- B → b [Terpenuhi]
- aD → Db [Terpenuhi, ukuran kedua ruas sama]
- aB → aa | aaAA [Terpenuhi]
- Ac → Bbcc [Terpenuhi]
Tipe 2 – Context Free Grammar
- Aturan produksi ini sama dengan tipe 0 namun a sisi kiri hanya boleh memiliki 1 variabel non terminal [|a| = 1] dan b tidak memiliki batasan
- a adalah sebuah simbol non terminal
- b dapat berupa rangkaian atau simbol terminal, non terminal atau epsilon
- tipe ini menghasilkan bahasa yang dikenali oleh Non Deterministic Push Down Automata
jadi aturan yang perlu diingat adalah:
- |a| = 1
- a adalah V
- b adalah [V+T]*
contoh:
- S → X a [Terpenuhi, di ruas kiri hanya ada satu non terminal yaitu S dan di ruas kanan boleh terminal atau non terminal]
- X → a [Terpenuhi]
- X → aX [Terpenuhi]
- X → abc [Terpenuhi]
- X → Є [Terpenuhi]
- S → AB [Terpenuhi]
- A → a [Terpenuhi, di ruas kiri hanya ada satu non terminal dan di ruas kanan ada satu terminal]
- B → b [Terpenuhi]
Tipe 3 – Regular Grammar
- Aturan S → Ɛ dibolehkan jika S tidak muncul pada ruas kanan setiap aturan
- α adalah sebuah simbol non terminal
- β adalah simbol terminal atau simbol terminal dengan sebuah simbol variabel yang jika ada terletak pada posisi paling kanan
- Menghasilkan bahasa yang dikenali oleh Finite State Automata
jadi perlu diingat:
- α adalah V
- β adalah T* atau T*V
Contoh:
- X → Ɛ
- X a | aY
- Y → b
- S → abB
- B → cd
Kesimpulan
Pada artikel ini kita telah membahas mengenai simbol Terminal dan Non Terminal, kemudian hirarki Chomsky serta Aturan Produksi yang digunakan. Oke teman teman semua terima kasih telah membaca.
Referensi:
Artikel ini merupakan hasil resume dari video PAKKODING [web, youtube].
Video berjudul #3 Teori Bahasa & Otomata – Tata Bahasa Hirarki Chomsky dan Aturan Produksi.
Terima kasih banyak ke pada PAKKODING atas materi yang disampaikan serta cara penyampaiannya yang mudah dipahami.