Sugeng Rawuh ^_^

" Mugi saking serat kedik menika saged maringi faedah kagem sederek sedaya"

Jumat, 21 Januari 2011

Makalah Push Down Automata

TEORI BAHASA DAN OTOMATA
“Push Down Automata”


Disusun oleh :
Rizki Tunjung Sari (09650006)
Ayu Dwi Noviyati (09650018)
Ratna Juwita (09650025)


PRODI TEKNIK INFORMATIKA
FAKULTAS SAINS DAN TEKNOLOGI
UIN SUNAN KALIJAGA YOGYAKARTA
2011
BAB I
PENDAHULUAN

Push Down Automata, selanjutnya kita sebut sebagai PDA, merupakan mesin otomata dari bahasa bebas konteks. Bila sebuah finite state automata berhingga mempunyai kemampuan “memori” yang berbatas, pada otomata push down atau Push Down Automata didefinisikan sebuah tempat penyimpanan yang tidak terbatas berupa stack/tumpukan.

Stack adalah kumpulan dari elemen-elemen sejenis dengan sifat penambahan elemen dan pengambilan elemen memalui suatu tempat yang disebut top of stack (puncak stack). Kita ingat bahwa sebuah stack diketahui top/puncaknya, dengan aturan pengisian LIFO (Last In First Out). Pengambilan elemen dari stack dinyatakan dengan operasi pop, sedang memasukkan elemen kedalam stack dengan operasi push. Setiap elemen stack bisa memuat satu symbol, yang pada push down automata disebut sebagai symbol stack.

Contoh sebuah stack:
Top stack →
A
D
E

Bila dilakukan operasi pop, maka kondisi stack menjadi:
Top stack →
D
E

Bila dilakukan operasi push B, maka kondisi stack menjadi:
Top stack →
B
D
E


BAB II
PEMBAHASAN

Push Down Automata (PDA)

PDA adalah mesin otomata dari TBBK yang diimplementasikan dengan stack sehingga hanya terdapat operasi “push” dan “pop” Stack (tumpukan) adalah suatu struktur data yang menggunakan prinsip LIFO (Last In First Out). Sebuah stack selalu memiliki top of stack dan elemen-elemen stack itu yang akan masuk ke dalam stack dengan method “push” dan akan keluar dari stack dengan method “pop”.

• Definisi : PDA adalah pasangan 7 tuple M = (Q, , , q 0 , Z 0 , , A), dimana :
Q : himpunan hingga stata, : alfabet input, : alfabet stack, q 0 Q : stata awal, Z0 : simbol awal stack, A Q : himpunan stata penerima, fungsi transisi : Q ({}) 2Q * (himpunan bagian dari Q x*)

• Untuk stata q  Q, simbol input a   , dan simbol stack X ,  (q, a, X) = (p, α) berarti : PDA bertransisi ke stata p dan mengganti X pada stack dengan string .

• Konfigurasi PDA pada suatu saat dinyatakan sebagai triple (q, x, α), dimana :
q Q : stata pada saat tersebut, x * : bagian string input yang belum dibaca, dan * : string yang menyatakan isi stack dengan karakter terkiri menyatakan top of
stack.

• Misalkan (p, ay, Xß) adalah sebuah konfigurasi, dimana : a  , y  *, X  , dan ß
*. Misalkan pula (p, a, X) = (q, ) untuk q Q dan *. Dapat kita tuliskan
bahwa : (p, ay, X)  (q, y, ).

Sebuah PDA dinyatakan dengan :
Q = himpunan state
 = himpunan simbol input
T = simbol stack
Δ = fungsi transisi
S = state awal
F = state akhir
Z = top of stack

PDA memiliki 2 jenis transisi, yaitu Δ yang menerima simbol input, simbol top of stack, dan state. Setiap pilihan terdiri dari state berikutnya dan simbol- simbol. Penggantian isi stack dilakukan dengan opersi push dan pop. Jenis transisi yang kedua adalah transisi ε. Transisi ε tidak melakukan pembacaan input namun hanya menerima simbol top of stack dan state. Transisi ini memungkinkan PDA untuk memanipulasi isi stack dan berpindah antar state tanpa membaca input.

Contoh PDA Deterministik:
PDA M = (Q, , , q0 , Z0 , , A) pengenal palindrome L = {xcxTx (ab)*}, dimana
xT adalah cermin(x), mempunyai tuple : Q = {q0 , q 1 , q 2 }, A = { q 2 }, = {a, b, c},
= {a, b, Z0 }, dan fungsi transisi terdefinisi melalui tabel berikut :



Sebagai contoh, perhatikan bahwa fungsi transisi No. 1 dapat dinyatakan sebagai : (q 0 , a, Z0 ) = (q 0 , aZ 0 ). Pada tabel transisi tersebut terlihat bahwa pada stata q 0 PDA akan melakukan PUSH jika mendapat input a atau b dan melakukan transisi stata ke stata q 1 jika mendapat input c. Pada stata q1 PDA akan melakukan POP.

Berikut ini pengenalan dua string oleh PDA di atas :
1. abcba : (q 0 , abcba, Z 0 )  (q 0 , bcba, aZ 0 ) (1)
 (q 0 , cba, baZ 0 ) (4)
 (q1 , ba, baZ 0 ) (9)
 (q1 , a, aZ 0 ) (11)
 (q1 , , Z 0 ) (10)
 (q 2 , , Z 0 ) (12) (diterima)
2. acb : (q 0 , acb, Z 0 )  (q 0 , cb, aZ 0 ) (1)
 (q1 , b, aZ0 ) (8), (crash ditolak)
3. ab : (q 0 , ab, Z 0 )  (q 0 , b, aZ0 ) (1)
 (q 0 , , baZ0 ) (4) (crash ditolak)

Penerimaan dan penolakan tiga string di atas dapat dijelaskan sebagai berikut :
1. string abcba diterima karena tracing sampai di stata penerima (q 2 ) dan string “abcba” selesai dibaca (string yang belum dibaca = )
2. string acb ditolak karena konfigurasi akhir (q 1 , b, a Z 0 ) sedangkan fungsi transisi
(q 1 , b, a) tidak terdefinsi
3. string ab ditolak karena konfigurasi akhir (q 0 , , baZ0 ) sedangkan fungsi transisi (q 0 ,, b) tidak terdefinsi

Ilustrasi graf fungsi transisi PDA di atas ditunjukkan melalui gambar berikut :

• Notasi (p, ay, X)  (q, y, ) dapat diperluas menjadi : (p, x, ) * (q, y, ), yang berarti konfigurasi (q, y, ) dicapai melalui sejumlah (0 atau lebih) transisi.
• Ada dua cara penerimaan sebuah kalimat oleh PDA, yang masing-masing terlihat dari konfigurasi akhir, sebagaimana penjelasan berikut :

Jika M = (Q, , , q 0 , Z 0 , , A) adalah PDA dan x *, maka x diterima dengan stata akhir (accepted by final state) oleh PDA M jika : (q 0 , x, Z0 ) * (q, , ) untuk * dan q A. x diterima dengan stack hampa (accepted by empty stack) oleh PDA M jika : (q 0 , x, Z0 ) * (q, , ) untuk q Q.

Contoh PDA Non-Deterministik:
PDA M = (Q, , , q 0 , Z0 , , A) pengenal palindrome L = {xx T x (ab)*} mempunyai komponen tuple berikut : Q = {q 0 , q1 , q 2 }, A = { q 2 }, = {a, b}, = {a, b, Z0 }, dan fungsi transisi terdefinisi melalui tabel berikut :


Pada tabel transisi tersebut terlihat bahwa pada stata q 0 PDA akan melakukan PUSH jika mendapat input a atau b dan melakukan transisi stata ke stata q 1 jika mendapat input .
Pada stata q 1 PDA akan melakukan POP. Dua contoh di atas menunjukkan bahwa PDA dapat dinyatakan sebagai mesin PUSH-POP.

Berikut ini pengenalan string “baab” oleh PDA di atas :
1. (q 0 , baab, Z 0 ) (q 0 , aab, bZ 0 ) (2 kiri)
 (q 0 , ab, abZ 0 ) (5 kiri)
 (q1 , ab, abZ 0 ) (3 kanan)
 (q1 , b, bZ0 ) (11)
 (q1 , , Z 0 ) (10)
 (q 2 , , Z 0 ) (12) (diterima)
2. (q 0 , baab, Z 0 )  (q1 , baab, Z 0 ) (2 kanan) (crash ditolak)
3. (q 0 , baab, Z 0 )  (q 0 , aab, bZ 0 ) (2 kiri)
 (q 0 , ab, abZ 0 ) (5 kiri)
 (q 0 , b, aabZ 0 ) (3 kiri)
 (q1 , b, aabZ 0 ) (4 kanan) (crash ditolak)
4. (q 0 , baab, Z 0 )  (q 0 , aab, bZ 0 ) (2 kiri)
 (q 0 , ab, abZ 0 ) (5 kiri)
 (q 0 , b, aabZ 0 ) (3 kiri)
 (q 0 , , baabZ 0 ) (4 kiri)
 (q1 , , baabZ 0 ) (9) (crash ditolak)


BAB III
PENUTUP

Pop/push dilakukan pada stack berdasarkan fungsi transisinya. Pop dan push untuk setiap kali transisi pada mesin Push Down Automata, dapat dilakukan pada lebih dari suatu symbol. Push down automata menerima dengan stack kosong maka himpunan state akhir.

Pengubahan tata bahasa bebas konteks ke bentuk normal Greibach lebih dulu untuk memudahkan mengkonstruksi Push Down Automata-nya. Pada final state push down automata kita tidak berkepentingan dengan kondisi stack setelah mencapai state akhir, sehingga kita tidak perlu membuat transisi untuk mengosongkan stack.

Minggu, 09 Januari 2011

Makalah As-Sunnah

MAKALAH PENGANTAR STUDI ISLAM
“STUDI AL-SUNNAH”

Disusun Oleh :

Ayu Dwi Noviyati

UIN SUNAN KALIJAGA YOGYAKARTA
FAKULTAS SAINS DAN TEKNOLOGI
TEKNIK INFORMATIKA
2009/2010
PENGANTAR

Puji syukur kehadirat Allah SWT , karena berkat rahmat dan karuniaNya makalah ini dapat kami selesaikan sesuai dengan yang diharapkan. Dalam makalah ini kami membahas tantang “Studi Al-Sunnah” yang mencakup beberapa metode untuk memahami al-sunnah dalam pengantar studi islam itu sendiri.
Makalah ini dibuat dalam rangka memperdalam pemahaman tentang “Studi Al-Sunnah” yang sangat diperlukan dalam studi keislaman dan sekaligus melakukan apa yang menjadi tugas mahasiswa yang mengikuti mata kuliah “Pengantar Studi Islam”.
Dalam proses pendalaman materi Pengantar Studi Islam, tentunya kami mendapatkan bimbingan, arahan, koreksi dan saran, untuk itu rasa terima kasih yang kami sampaikan kepada:
• Drs. Kamsi, M.A., selaku dosen mata kuliah “Pengantar Studi Islam”.
• Rekan-rekan mahasiwa yang telah banyak memberikan masukan untuk makalah ini.
Demikian makalah ini kami buat semoga bermanfaat.

Yogyakarta, Desember 2010

Penyusun


BAB I
PENDAHULUAN


Pengertian Sunnah
Pengertian sunnah dapat dilihat dari dua hal, yaitu secara etimologi dan terminology. Secara etimologi, sunnah berarti tata cara. Menurut Lisan al-‘Arab, sunnah pada mulanya berarti jalan atau cara, yaitu jalan yang dilalui orang-orang dahulu kemudian di ikuti oleh orang-orang belakangan. Sementara itu dalam Mukhtar al-Sihah, sebagaimana dikutip oleh Azami, sunnah secara etimologi berarti tata cara dan tingkah atau perilaku hidup, baik perilaku itu terpuji maupun tercela.
Sementara itu, terdapat beragam pendapat tentang pengertian sunnah menurut terminology. Menurut ahli hadis, sunnah berarti sabda, pekerjaan, ketetapan, sifat (watak budi atau jasmani); atau tingkah laku Nabi Muhammad saw, baik sebelum menjadi Nabi maupun sesudahnya. Dalam konteks ini, pengertian sunnah sama dengan hadis. Sementara itu, menurut kalangan ahli usul fiqih, sunnah diartikan sebagai sabda Nabi Muhammad saw yang bukan berasal dari al-Qur’an, pekerjaan, atau ketetapannya. Agak serupa dengan pendapat kedua, menurut ahli fiqih sunnah dimaknai sebagai hal-hal yang berasal dari Nabi Muhammad saw baik berupa ucapan maupun pekerjaan, tetapi hal itu tidak wajib dikerjakan.
Dalam al-Qur’an dan sabda Nabi juga terdapat beberapa kata sunnah. Paling tidak ada empat tempat dalam al-Qur’an yang memuat kata sunnah, yaitu Q.S al-Nisa’:26, Q.S al-Anfal:38, Q.S al-Isra:77, dan Q.S al-Fath:23.
Terhadap kata sunnah dalam tiga surat yang lain Ibnu Katsir memaknai kata sunnah dalam surat al-Anfal dengan aturan Allah yang diberlakukan terhadap orang-orang dahulu, sementara dalam surat al-Isra diartikan sebagai ketetapan (aturan) Allah terhadap orang-orang yang mengingkari rasul-rasulNya, dan dalam surat al-Fath ditafsirkan dengan sunnatullah dan kebiasaan Allah yang diterapkan kepada makhlukNya. Dengan demikian, kata sunnah dalam al-Qur’an lebih berarti tata cara dan kebiasaan.
As-Sunnah sendiri secara bahasa mempunyai pengertian yaitu:
1) Jalan yang ditempuh
2) Cara atau jalan yang sudah terbiasa
3) Sebagai lawan dari kata bid’ah
Sedangkan sunnah menurut istilah syar’I adalah:

Artinya:
Sesuatu yang berasal dari Rasulullah saw, baik berupa perkataan, perbuatan, maupun penetapan pengakuan.
Dengan pengertian seperti ini, maka yang dimaksud dengan as-sunnah ialah segala sesuatu yang diperhatikan, dilarang, atau dianjurkan oleh Rasulullah saw baik berupa perkataan (qauli), perbuatan (fi’li) maupun ketetapannya (taqriri). Dengan demikian as-sunnah dijadikan pedoman hidup setelah Al-qur’an dan kita sering mendengar orang menyebut dalil-dalil syari’at dari Al-qur’an dan As-sunnah, itu maksudnya adalah Al-qur’an dan al-hadist.
Para ulama menafsirkan kata as-sunnah itu mempunyai makna yang berbeda-beda sesuai dengan disiplin ilmunya masing-masing, seperti perbedaan diantara ulama ahli hadist, ahli usul fiqih, dan para ahli fiqih dalam memaknai as-sunnah. Perbedaan makna yang dimaksud adalah:
a) Menurut ulama ahli hadist, kata “As-Sunnah” maknanya adalah semua yang dinukil dari Nabi saw, yang berupa perkataan, perbuatan, dan sifat. Artinya semua yang datang dari Nabi disebut As-sunnah.
b) Menurut istilah ulama ushul fiqih makna “As-sunnah” yaitu segala sesuatu yang datang dari Nabi berupa perkataan, perbuatan, dan ketetapan yang bisa dijadikan sebagai dalil syar’i. Ini berarti semua yang tidak dapat dijadikan sebagai dasar hukum sayari’at menurut ulama ushul fiqih tidak disebut as-sunnah.
c) Menurut ulama fiqih, kata “As-sunnah” maknanya adalah semua amalan yang apabila dikerjakan mendapat pahala dan bila ditinggalkan tidak mendapatkan siksa. Atau sesuatu yang diperintahkan namun tidak diwajibkan.



BAB II
ISI

Dasar As-sunnah sebagai Sumber Hukum Islam
Untuk mengetahui dasar-dasar bahwa as-sunnah itu sebagai sumber hokum islam, kita dapat memperhatikan dalil-dalil berikut ini.
1) Dalil Al-qur’an
Didalam Al-quran Allah menjelaskan kehujahan sunnah Nabi dengan berbagai cara, salah satu diantaranya memerintahkan orang yang beriman untuk mengembalikan perselisihan pendapat yang terjadi diantara mereka kepada Allah dan RasulNya. Sesuai dengan firman Allah yang tertulis pada surat An-nisa:59


Artinya:
“Taatilah Allah dan taatilah Rasul dan ulil amri diantara kamu. Kemudian jika kamu berlainan pendapat tentang sesuatu, maka kembalikanlah ia kepada Allah dan Rasulnya”
Menurut dalil Al-qur’an diatas bahwa yang dimaksud mengembalikan kepada Allah yaitu berarti mengembalikan suatu permasalahan kepada Al-qur’an, dan mengembalikan sesuatu kepada Rasul adalah mengembalikan kepada sunnah Rasul.
2) Dalil Al-hadist
Selain Al-qur’an, al-hadist juga menjelaskan tentang kedudukan as-sunnah sebagai sumber hokum islam, antara lain:

Artinya:
“Aku tinggalkan dua pusaka untukmu sekalian, yang kalian tidak akan tersesat selagi berpegang teguh kepada keduanya yaitu kitab Allah dan sunnah RasulNya”
Hadist tersebut diatas menjelaskan kepada kita bahwa umat islam wajib berpegang teguh kepada keduanya yaitu kitab Allah dan sunnah RasulNya.
3) Kesepakatan para ulama (ijma’)
Umat islam telah sepakat menjadikan sunnah sebagai salah satu hokum beramal, karena sesuai yang dikehendaki RasluNya. Mereka menerima sunnah seperti halnya mereka menerima Al-qur’an. Keduanya dijadikan sumber hokum dalam islam.
Kesepakatan umat islam dalam mempercayai dan menerima serta mengamalkan segala ketentuan yang terkandunga dalam as-sunnah terus berlanjut sejak masa Rasul masih hidup. Sepeninggal beliau, mulai zaman Khulafa Al-Rasyidin hingga masa-masa selanjutnya, dan tidak ada yang mengingkarinya.
4) Sesuai dengan petunjuk akal
Secara akal pun dapat dinyatakan bahwa konsekuensi mempercayai Muhammad sebagai Rasul Allah mengharuskan menerima dan mentaati segala yang beliau perintahkan dan yang beliau larang. Suatu kepercayaan tanpa dibarengi oleh penerimaan dan ketaatan terhadap apa yang dipercayai adalah bohong semata.

Kedudukan dan Fungsi Sunnah
Kedudukan dan fungsi sunnah dapat dilihat melalui firman Allah dalam al-Qur’an. Menurut Azami, paling tidak ada empat kedudukan dan fungsi sunnah dalam islam.
1) Menjelaskan Kitabullah
Diantara tugas Rasulullah saw adalah menjelaskan hal-hal yang masih global (mujmal) dalam al-Qur’an. Banyak ayat al-Qur’an yang masih memerlukan penjelasan praktis. Karena itu, Rasulullah tidak dapat dilepaskan dari tugas ini. Tentu saja penjelasan terhadap kandungan al-Qur’an bukan sekedar “membaca al-Qur’an”. Menolak penjelasan Rasulullah sama saja dengan menolak perintah Allah yang ditegaskan dalam al-Qur’an. Tentang tugas ini paling tidak tercemin dalam Q.S al-Nahl:44 yang artinya, “Dan kami turunkan kepadamu al-Qur’an, agar kamu menerangkan kepada umat manusia apa yang telah diturunkan kepada mereka, dan supaya mereka memikirkan.”
2) Rasulullah sebagai uswatun hasanah
Kedudukan Rasulullah sebagai contoh bagi umat manusia (Islam) setidaknya tercermin dari perintah Allah dalam Q.S al-Ahzab:21, “sesungguhnya telah ada pada (diri) Rasulullah itu suri tauladan yang baik bagimu, yaitu bagi orang yang mengharap rahmat Allah dan kedatangan hari kiamat dan ia banyak menyebut Allah.” Makna mencontoh disini melalui apa yang dikatakan, diperbuat, dan ditetapkan oleh Rasulullah, meskipun tidak sekedar dalam pengertian harfiyah, namun bagaimana cara dan model berfikir Rasulullah dalam menyelesaikan sebuah persoalan dapat dicontoh untuk mengatasi berbagai persoalan mutakhir.
3) Rasulullah wajib ditaati
Mentaati Rasulullah sama dengan mentaati Allah, sebab apa yang diperintahkan Allah dalam al-Qur’an.
4) Rasulullah mempunyai kewenangan membuat aturan.

Wilayah Kajian al-Sunnah
Bahasan studi al-Sunnah pun tidak kalah banyaknya dengan studi tentang al-qur’an. Topik-topik bahasan al-Sunnah dapat digambarkan demikian;
Pertama, tentang pengertian hadis, sunnah, khabar, athar, dan hadis kudsi. Masuk pula didalamnya klasifikasi hadis dari segi banyak dan sedikitnya perowi, yang meliputi: (1) hadis mutawatir dan hadis ahad, dan klasifikasi hadis ahad kepada sahih, hasan, dan dho’if.
Kedua, sejarah dan perkembangan pembukuan hadis, mulai dari priode pertama (masa nabi) sampai sekarang.
Ketiga, berbicara tentang macam-macam kitab hadis dan derajatnya.
Keempat, tentang cabang-cabang ilmu hadis, yang meliputi ilmu rijal al-hadis, ilmu jarh wa al-ta’dil, ilmu ‘ilal al-hadis, ilmu gharib al-hadis, ilmu nasikh wa al-mansukh, ilmu asbab al-wurud al-hadis, dll.
Kelima, ilmu mustolah hadis, yang meliputi maratanrai (transmitor / sanad) dan isi hadis (matan).
Keenam, bahasan tentang unsur-unsur yang harus ada dalam menerima hadis, yaitu: (1) perowi, (2) matan, dan (3) sanad.
Dari bahasan tersebut dapat disimpulkan bahwa ada dua kriteria untuk menilai hadis, yakni: (1) lewat rantaian yang meriwayatkan hadis (perowi), dan (2) isi dari hadis (matan hadis).

BAB III
PENUTUP

Dari pembahasan diatas, dapat disimpulkan bahwa yang dimaksud dengan As-sunnah sebagai sumber hukum islam ialah bahwa selain terhadap Al-qur’an, seluruh umat islam wajib menjadikan sunnah sebagai pedoman dan pandangan hidup, dan menyandarkan segala permasalahan hidupnya kepada sunnah. Jadi seorang muslim tidak mungkin memahami syari’at islam ataupun mengambil suatu dalil tanpa kembali kepada kedua sumber hukum tersebut. Apabila terjadi seperti demikian, maka orang tersebut dinyatakan sesat.
Ibnu Badrun berkata: setiap orang yang berpengetahuan mengetahui bahwa tetapnya kehujahan sunnah dalam menetapkan hokum adalah hal pokok dalam agama, dan tidak mengingkari hal tersebut kecuali orang yang merugi dalam islam.



DAFTAR PUSTAKA

Nasution, Khoiruddin. 2009. Pengantar Studi Islam. Yogyakarta: ACAdeMIA+Tazzafa.

Darmawan, Andy, M.Ag. 2005. Pengantar Studi Islam. Yogyakarta: Pokja Akademik UIN Sunan Kalijaga.