Manakah dari aturan produksi di bawah ini yang merupakan aturan produksi Context Sensitive
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 Show 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 terminalApa itu simbol terminal?
yang termasuk simbol terminal:
Apa itu simbol NON terminal (Variabel)?
yang termasuk simbol NON terminal (variabel):
Aturan ProduksiDalam teori bahasa dan otomata, aturan produksi dinyatakan dalam: α → β (dibaca: alpha menghasilkan atau menurunkan beta)
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 ChomskyGrammar
4 tingkatan tata bahasa menurut Chomsky:
Tipe 0 – Unrestricted Grammar
jadi aturan yang perlu diingat adalah:
Contoh penerapan aturan tipe 0:
Tipe 1 – Context Sensitive Grammar
jadi aturan yang perlu diingat adalah:
Contoh penerapan:
Tipe 2 – Context Free Grammar
jadi aturan yang perlu diingat adalah:
contoh:
Tipe 3 – Regular Grammar
jadi perlu diingat:
Contoh:
KesimpulanPada 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. |