Minggu, 28 November 2010

Hari ini diminta untuk mengawasi ujian Pemrograman berbasis Web mahasiswa P2k, kebetulan mahasiswanya tidak asing dengan saya, karena mereka juga pernah saya ajar di Mata Kuliah Peng. Teknologi dan Informasi. Seperti biasa, didetik2 terakhir, mahasiswa mulai ribut berusaha mencari jawaban dari kanan kiri... kadang aku sedih, mereka melakukannya dengan terang2an, tanpa malu.... apakah mereka sadar bahwa perbuatan menyontek itu sama dengan perbuatan mencuri dan korupsi? sementara Mahasiswa sekarang katanya paling anti atau musuh koruptor...
Jujur dalam hati, saya lebih senang kalau diminta untuk mengajar anak sekolah atau mahasiswa reguler, yang mana mahasiswa tersebut memang meneruskan kuliah karena mereka baru lulus dari sekolah, bukan mahasiswa yang telah mencicipi dunia kerja terlebih dahulu. Mahasiswa yg fresh graduate, rasa haus akan ilmunya jauh lebih besar dibanding mereka yang sudah mengetahui enaknya cari uang... memang tidak semua mahasiswa yang notabene karyawan itu begitu, ada juga mahasiswa karyawan yang dewasa, artinya mahasiswa tersebut tahu dan bisa menempatkan statusnya, kapan dan apa yg seharusnya dia lakukan jika dia sedang berstatus mahasiswa atau karyawan.
Banyak suka duka yang dialami bila mengajar mahasiswa karyawan, mereka banyak menuntut tanpa mau melihat dan membenahi dulu dirinya, dan yang naifnya sistem yang tidak sistematis malah kadang hanyut terbawa arus yang salah. Contohnya : sistem pengajaran seharusnya mempunyai tim yang bertugas membuat SAP dan modul, sehingga Mahasiswa yg statispun bisa belajar walaupun cuma bisa menghapal saja. Satu lagi yang fatal, aturan yang sebenarnya mengakui adanya mata kuliah prasyarat tp pada kenyataannya di perkuliahan karyawan ada dispensasi shg mahasiswa bisa mengambil matakuliah semaunya semampunya, alhasil nilai jeblog semua, bagaimana tidak jeblog? matakuliah pra syaratnya belum diambil atau sedang diambil tapi sudah mengikuti matakuliah lanjutannya.... bagaimana bisa??
Prihatin dengan semangat mahasiswa saat ini yang notabene adalah seorang pemuda, seharusnya pemuda itu merupakan pilar bangsa kedepannya, tapi sudah disemaikan benih kecurangan.... mereka lupa akan pertanggungjawaban di hari akhir nanti, dimana semua orang tidak bisa mengelak apalagi menghindarinya. Andaikata tiap insan manusia sadar bahwa dia hidup didunia hanya sebagai hamba yang selalu "mengabdi" kepada "majikannya" (ibadah) dan selalu dipantau gerak geriknya untuk dibuat buku raportnya.... pastilah dia akan takut untuk berbuat salah.

BERSIHKAN Ginjal ANDA DENGAN HARGA KURANG DARI $ 1,00

Bertahun-tahun berlalu dan ginjal kita menyaring darah dengan membuang garam,racun dan yang tidak diinginkan memasuki tubuh kita.
Seiring berjalannya waktu, terjadi akumulasi garam dan hal ini memerlukan perawatan pembersihan.
Bagaimana kita akan melakukan ini?
Sangat mudah, pertama-tama ambil seikat peterseli dan cucilah sampai bersih
Kemudian dipotong dalam potongan-potongan kecil dan masukkan ke dalam panci lalu tuangkan air bersih dan didihkan selama sepuluh menit dan biarkan dingin dan kemudian saring dan tuangkan dalam botol yang bersih dan simpan di dalam lemari es hingga dingin.
Minum satu gelas setiap hari dan Anda akan melihat semua akumulasi garam dan racun lain yang keluar dari ginjal Anda dengan buang air kecil. Anda juga akan melihat perbedaan yang tidak pernah rasakan sebelumnya.
Peterseli dikenal sebagai pengobatan terbaik untuk membersihkan ginjal dan itu ALAMI!

RS Hewan Pemerintah Ragunan

Hari ini berhasil memeriksakan Tobo-Tobi (seekor kucing @2 tahun-an) dan Brownies (seekor kelinci 4 bulan) ke dokter hewan di Ragunan. Karena Tobi lagi flu, maka Tobo dan Tobi tidak di vaksin, menunggu flu Tobi sembuh dulu, oleh sebab itu Tobi diberi obat flu dan vitamin, dan Tobo diberi vitamin B komplek dan tulang, supaya tulangnya kuat... kurang lebih 1 bulan lagi Tobo dan Tobi baru mulai di vaksin untuk kemudian diberi anti rabies. Sementara itu brownies hanya diberi vitamin C dan B komplek juga suntikan anti penyakit kulit yang rutin harus diberikan selama 5 hari.... Kelinci itu perawatannya cukup mudah karena tidak ada vaksin ini itu, hanya vitamin dan anti penyakit kulit (jika ada tanda2 sakit kulit) saja yg dibutuhkan, yang penting makanannya dan hidupnya jgn di tempat basah...

Ekspresi Regular

• Sebuah bahasa dinyatakan Regular jika terdapat Otomata Hingga yang dapat menerimanya
• Ekspresi regular memungkinkan mendefinisikan bahasa-bahasa.
• Ekspresi Regular memberikan suatu pola untuk untai/string dari suatu bahasa. Untai yang menyusun suatu bahasa regular akan cocok dengan pola bahasa itu.
• Banyak masalah pada perancangan software yang bisa disederhanakan dengan melakukan pengubahan notasi ekspresi regular ke dalam implementasi komputer dari Otomata Hingga yang bersangkutan. Seperti : Pencarian string pada suatu file (ada pada text editor).
• Contoh penerapan lain adalah pembatasan data masukan yang diperkenankan, misalnya suatu field input hanya menerima input bilangan 0..9 seperti gambar berikut :

Note :
Gambar ini menerima input antara 0 sampai 9, sedangkan ekspresi regularnya dinyatakan sebagai berikut : (digit) (digit)*
digit = 0..9

• Dalam suatu kompilator, ekspresi regular dapat diaplikasikan untuk melakukan analisis leksikal , yaitu mengidentifikasi unit-unit leksikal yang dikenal dalam program. Unit leksikal ini bisa disebut dengan token.
• Token-token pada bhs pemrograman kebanyakan tanpa kecuali dinyatakan sebagai ekspresi regular. Misal suatu identifier.

Notasi ekspresi regular

Notasi dasar ekspresi regular antara lain :

• Cleen Closure (*) → termasuk hampa
• Positive Closure (⁺) → tanpa hampa
• Union ( ∪ atau + ) → berarti atau
• Concatenation ( . ) → gabungan, notasi bisa tidak ditulis

Hubungan Ekspresi Regular dengan Otomata Hingga

Untuk setiap ekspresi regular ada satu AHN dengan transisi ε yang equivalen. Artinya kita dapat membuat suatu AHN-ε dari suatu ekspresi regular.


Contoh :

AHN-ε untuk ekspresi Regular ab




Aturan Produksi Untuk Suatu Otomata Hingga

• Selain dgn ekspresi regular, bisa dgn mengkonstruksikan aturan-aturan produksi untuk suatu tata bahasa regular (Regular Grammar) dari suatu otomata Hingga
  
  α → β
  
• Seperti yang sudah kita pelajari sebelumnya bahwa grammar itu terdiri dari 4 tupel, yaitu :
  
  G(V_T, V_N, S, P)
  
  
• Lalu bagaimana mengkonstruksi aturan produksinya?
  
  sebelum melangkah lebih jauh, ada beberapa hal yang harus diketahui :
  
  1. Stata awal = S, Simbol Input = V_T, Simbol Stata =V_N (termasuk S dan Z).
  2. Jika Stata awal diberi input a menuju ke stata X, dan X bukan stata penerima maka notasinya menjadi S → aX
  3. Jika suatu stata, misal Y, diberi input e menuju stata Q, maka notasinya menjadi Y → Q
  4. Jika Y diberi input a menuju ke stata penerima, dan pada stata penerima tidak ada lagi busur keluar, maka notasinya menjadi Y → a
  5. Tapi jika Y diberi input a menuju ke stata penerima, dan pada stata penerima terdapat busur keluar, maka notasinya menjadi Y → ε
  6. Jika Y diberi input a menuju ke stata Q, dan dari Q tidak ada transisi keluar dan bukan pula stata penerima, maka transisi ke Q dapat diabaikan.

CONTOH :
Konstruksikan aturan produksi untuk otomata berikut :

Otomata Hingga Untuk Suatu Regular Grammar

Dalam membentuk Otomata hingga dari Regular Grammar, ada algoritma yang harus diperhatikan, yaitu

1. Tetapkan input pada Otomata Hingga = input pada Regular Grammar yang selanjutnya ditulis V_T(AHN) = V_T(RG). Begitu pula dgn Stata awal, S(AHN) = S(RG)
2. Produksi Ap → a Aq equivalen dengan M(Ap,a) = Aq
   
   Produksi Ap → a equivalen dengan M(Ap,a) = X, X ∉ VN. Sehingga V_N(AHN) = X ∪ V_N(RG).
3. Ketentuan pada pembentukan grammar regular juga berlaku pada pembentukan otomata hingga.

Contoh :


Misalkan terdapat Grammar Regular dengan aturan produksi sebagai berikut:

S → aB | bA | ε
A → abaS
B → babS
Gambarkan Otomata Hingganya!

Equivalensi

Ekivalensi Otomata Hingga

Ekivalensi AHN menjadi AHD

Mesin Otomata Non deterministik (AHN) dapat dibuat menjadi mesin otomata Deterministik (AHD) yang ekivalen. Adapun algoritma pembentukan AHD dari AHN adalah sebagai berikut :

1. Tetapkan S(AHD) = S(AHN) & V_T(AHD) = V_T (AHN)
2. Copykan tabel AHN sbg tabel AHD, mula-mula K(AHD) = K(AHN) dan M(AHD) = M(AHN)
3. Setiap stata yang merupakan nilai dari fungsi M(AHN) namun stata tersebut bukan elemen dari K(AHN), maka tetapkan sbg elemen baru dari K(AHD). Tempatkan stata tsb pd kolom stata M(AHD). Lakukan pemetaan berdasarkan fungsi M(AHN).
4. Ulangi langkah 3 sampai tidak diperoleh stata baru
5. Z(AHD) = semua stata yang mengandung stata elemen Z(AHN).

Contoh :

Buatlah AHD yg ekivalen dengan AHN berikut :

EKIVALENSI 2 AHD

Sama halnya dengan ekivalensi AHN-e ke bentuk AHN dan ekivalensi dari AHN ke AHD; AHD,yang kemudian disebut sebagai OTOMATA ,dapat dibuat ekivalensinya sehingga mesin yang secara fisik berbeda namun sama-sama dapat menerima bahasa  [L(G)] yang sama, dapat diubah bentuknya tanpa merubah arti.

ALGORITMA :

Algoritma untuk menguji ekivalensi 2 AHD :

1.     Pastikan nama stata berbeda pada masing2 AHD

2.     Buat tabel antara pasangan terurut

            (Stata AHD A, Stata AHD A’) lengkap dgn input-inputnya

3.     Pasangan Terurut pertama diisi dgn stata awal masing2 AHD

4.     Perhatikan nilai-nilai pasangan terurut pada baris pertama, jika terdapat nilai pasangan terurut yang tidak sama, tempatkan nilai tersebut sebagai pasangan terurut baru. Dan seterusnya…

5.     Jika tidak ada lagi pasangan terurut baru, maka proses dihentikan dan kedua AHD tersebut dinyatakan ekivalen

Contoh :

Apakah Kedua AHD di bawah ini ekivalen? Buktikan !

1. Jika diketahui :

            K         = {q₀, q₁},   V_T = { a },   S = q₀,   Z = { q₁ }

            M         => (q₀, a) = q₁  (q₁, a) = q₀

            - Gambarkan grafnya

            - Tentukan bahasa yang dihasilkan, L(G)?

2. Jika diketahui :

            K         = {q₀, q₁},   V_T = { a },   S = q₀,   Z = { q₁ }

            M         => (q₀, a) = q₁  (q₁, a) = q₁

            Gambarkan grafnya & Tentukan L(G) nya

HIRARKI CHOMSKY

Teori Otomata berkaitan erat dgn teori bahasa formal.
Ada beberapa hal yang berkaitan dengan Otomata, yaitu Grammar. Grammar adalah bentuk abstrak yang dapat diterima (accept) untuk membangkitkan suatu kalimat otomata berdasarkan suatu aturan tertentu.

Grammar G didefinisikan sebagai pasangan 4 tuple, G(Vt , Vn , S, P) :

1. Himpunan Simbol Terminal (Vt).

    Derivasi akan berakhir jika sentensial yang dihasilkan adalah sebuah kalimat yang tersusun atas simbol-simbol terminal. Sentesial adalah string yang tersusun atas simbol terminal atau simbol non terminal atau campuran keduanya.
Yang termasuk dalam simbol terminal diantaranya :

   1.      Huruf kecil anggota alfabet à kalimat à Bahasa

   2.      Simbol Operator (+, -, *, ^)

   3.      Simbol tanda baca (titik dan Koma, ?, !)

   4.      String yang dicetak tebal, seperti if, then, dan else.   

2.  Himpunan simbol Nonterminal (Vn)

     Yang termasuk dalam simbol Nonterminal :

1. Huruf Besar (kapital)
2. Simbol Awal/Start, misal S
3. String yang dicetak miring, seperti expr.

3. Simbol Start (S), dimana simbol ini merupakan bagian dari simbol Nonterminal.

4. Himpunan Produksi (P)

    Bentuknya aàb yang artinya ruas kiri produksi (a) menurunkan ruas kanan produksi (b)

Tahun 1959 seorang ahli bernama Noam Chomsky melakukan penggolongan tingkatan bahasa menjadi empat tipe, yaitu :

Keterangan Symbol :
* disebut juga cleene closure
 | disebut juga alternate

Pe eR AHD dan AHN

Diketahui Otomata Hingga Deterministik sebagai berikut :

Pertanyaan:

1. Tentukan Komponen-komponennya
2.  Sajikan dalam bentuk table
3. Tentukan pula L(G)nya

Diketahui Otomata hingga Nondeterministik sebagai berikut :

Pertanyaan:

1. Tentukan Komponen-komponennya
2. Sajikan dalam bentuk table
3. Lakukan tracing terhadap input 101010, 00111, 0101000, 11111; bagaimana hasilnya?
4. Tentukan pula L(G)nya