tugas sbd2

SISTEM BASIS DATA 2

PENGENALAN DBMS

KELAS 3IA08

ANGGOTA :

Abdullah Omar (50407006)

Devi Triwulandari (50407255)

Karina Adriani (50407487)

Nur Endah Sari (50407632)

UNIVERSITAS GUNADARMA

2010

TEORI BAHASA DAN AUTOMATA

Tujuan Perancangan Basis Data

Sekarang kita fokuskan ke siklus sistem aplikasi basisi data yaitu desain basis data. Tujuan desain basis data adalah :

• Memenuhi kebutuhan isi informasi dari pemakai dan aplikasi tertentu.

• Menyediakan struktur informasi alami dan mudah dipahami.

• Mendukung kebutuhan pemrosesan dan performansi obyektif seperti response time, processing time dan storage space.

Terdapat enam tahap utama pada proses desain basis data yaitu :

1. Koleksi dan analisa kebutuhan

2. Desain basis data konseptual

3. Pemilihan DBMS

4. Pemetaan model data (disebut juga desain basis data logika)

5. Desain basis data fisik.

6. Implementasi dan tuning sistem basis data

Proses desain terdiri dari dua aktifitas paralel. Aktifitas pertama meliputi desain data content dan struktur basis data, kedua berhubungan dengan aplikasi basis data.

Enam tahap diatas tidak diproses secara berurutan. Pada beberapa kasus mungkin memodifikasi desain dari awal tahap selama tahap kemudian. Feedback loop antar tahap juga dalam tahap sering terjadi. Summary tahap 2, 4, dan 5 adalah berikut :

• Desain basis data konseptual (Tahap 2) : Tujuan dari tahap ini adalah memproduksi skema konseptual untuk basis data yang independen dari DBMS tertentu. Biasanya menggunakan model data tingkat tinggi seperti model ER atau EER.

• Pemetaan model data (Tahap 4) : Selama tahap ini yang djuga disebut desain basis data logika, dilkaukan pemetaan skema konseptual dari model data tingkat tinggi ke model data DBMS.

Aplikasi Basis Data dalam Life Cycle

Siklus kehidupan sistem informasi sering disebut macro life cycle, dimana siklus kehidupan basis data merupakan micro life cycle.

Aktifitas-aktifitas yang berhubungan dengan basis data sebagai micro life cycle dan termasuk fase-fasenya sbb :

1. Database planning

Di aktifitas ini akan disusun bagaimana langkah-langkah siklus hidup dapat direalisasikan secara lebih efisien dan efektif.

2. System definition

Definisi ruang lingkup basis data (misal : para pemakai, aplikasi-aplikasinya, dsb.)

3. Design

Pada bagian dari fase ini, perancangan sistem basis data secara konseptual, logikal dan fisik dilaksanakan

4. Implementation

Pemrosesan dari penulisan definisi basis data secara konseptual, eksternal, dan internal, pembuatan file-file basis data yang kosong, dan implementasi aplikasi-aplikasi software.

5. Loading atau Data Conversion

Basis data ditempatkan baik secara memanggil data secara langsung ataupun merubah file-file yang ada ke dalam format sistem basis data dan memangggilnya kembali.

6. Application Conversion

Beberapa aplikasi software dari suatu sistem sebelumnya dikonversikan ke suatu sistem yang baru.

7. Testing dan Validation

Sistem yang baru ditest dan diuji kebenarannya.

8. Operation

Operasi-operasi pada sistem basis data dan aplikasi-aplikasinya.

9. Monitoring dan Maintenance

Selama fase operasi, sistem secara konstan memonitor dan memelihara basis data. Pertambahan dan pengembangan data dan aplikasi-aplikasi software dapat terjadi. Modifikasi dan pengaturan kembali basis data mungkin diperlukan dari waktu ke waktu.

Langkah ke-3 disebut juga perancangan basis data. Langkah 3, 4, dan 5 merupakan bagian dari fase design dan implementation pada siklus kehidupan sistem informasi yang besar. Pada umumnya basis data pada organisasi menjalani seluruh aktifitas-aktifitas siklus kehidupan di atas. Langkah 5 dan 6 tidak berlaku jika basis data dan aplikasi-aplikasinya baru.

Proses Perancangan Basis data

6 Fase proses perancangan basis data :

1. Pengumpulan data dan analisis

2. Perancangan basis data secara konseptual

3. Pemilihan DBMS

4. Perancangan basis data secara logika (data model mapping)

5. Perancangan basis data secara fisik

6. Implementasi Sistem basis data.

Gambar fase-fase perancangan basis data untuk basis data yang besar :

Keterangan :

Secara khusus proses perancangan berisikan 2 aktifitas paralel. Aktifitas yang pertama melibatkan perancangan dari isi data dan struktur basis data, sedangkan aktifitas kedua mengenai perancangan pemrosesan basis data dan aplikasi-aplikasi perangkat lunak.

Dua aktifitas ini saling menjalin, misalnya : kita dapat mengidentifikasikan data item yang akan disimpan dalam basis data dengan menganalisa aplikasi-aplikasi basis data. Dua aktifitas ini juga saling mempengaruhi satu sama lain. Contohnya : fase perancangan basis data secara fisik, pada saat kita memilih struktur penyimpanan dan jalur-jalur akses dari file-file basis data yang tergantung pada aplikasi-aplikasi yang akan menggunakan file-file tsb.

Di lain pihak, kita biasanya menentukan perancangan aplikasi-aplikasi basis data dengan mengarah kepada konstruksi skema basis data yang telah ditentukan selama aktifitas yang pertama.

6 fase di atas tidak harus diproses berurutan. Pada beberapa hal, rancangan tsb dapat dimodifikasi dari yang pertama dan sementara itu mengerjakan fase yang terakhir (feedback loop antara fase) dan feedback loop dalam fase sering terjadi selama proses perancangan.

Fase 1 merupakan kumpulan informasi yang berhubungan dengan penggunaan basis data. Fase 6 merupakan implementasi basis datanya. Fase 1 dan 6 kadang-kadang bukan merupakan bagian dari perancangan basis data, tetapi merupakan bagian dari siklus kehidupan sistem informasi secara umum. Inti dari proses perancangan basis data adalah fase 2, 4, 5

Fase 1 : Pengumpulan data dan analisa

Proses identifikasi dan analisa kebutuhan-kebutuhan data disebut pengumpulan data dan analisa. Untuk menentukan kebutuhan-kebutuhan suatu sistem basis data, pertama-tama harus mengenal bagian-bagian lain dari sistem informasi yang akan berinteraksi dengan sistem basis data, termasuk para pemakai yang ada dan para pemakai yang baru serta aplikasi-aplikasinya. Kebutuhan-kebutuhan dari para pemakai dan aplikasi-aplikasi inilah yang kemudian dikumpulkan dan dianalisa.

Aktifitas-aktifitas pengumpulan data dan analisa :

1. Menentukan kelompok pemakai dan bidang-bidang aplikasinya

Menentukan aplikasi utama dan kelompok user yang akan menggunakan basis data. Individu utama pada tiap-tiap kelompok pemakai dan bidang aplikasi yang telah dipilih merupakan peserta utama pada langkah-langkah berikutnya dari pengumpulan dan spesifikasi data.

2. Peninjauan dokumentasi yang ada

Dokumen yang ada yang berhubungan dengan aplikasi-aplikasi dipelajari dan dianalisa. Dokumen-dokumen lainnya (seperti : kebijaksanaan-kebijaksanaan, form, report, dan bagan organisasi) diuji dan ditinjau kembali untuk menguji apakah dokumen-dokumen tsb berpengaruh terhadap kumpulan data dan proses spesifikasi.

3. Analisa lingkungan operasi dan pemrosesan data

Informasi yang sekarang dan yang akan datang dipelajari. Termasuk juga analisa jenis-jenis transaksi dan frekuensi-frekuensi transaksinya dan juga arus informasi dalam sistem. Input-output data untuk transaksi-transaksi tsb diperinci.

4. Daftar pertanyaan dan wawancara

Tuliskan tanggapan-tanggapan dari pertanyaan-pertanyaan yang telah dikumpulkan dari para pemakai basis data yang berpotensi. Ketua kelompok (individu utama) dapat diwawancarai sehingga input yang banyak dapat diterima dari mereka dengan memperhatikan informasi yang berharga dan mengadakan prioritas.

Fase 2 : Perancangan basis data secara konseptual

Tujuan dari fase ini adalah menghasilkan conceptual schema untuk basis data yang tergantung pada sebuah DBMS yang spesifik. Sering menggunakan sebuah high-level data model seperti ER/EER model selama fase ini. Dalam conceptual schema, kita harus memerinci aplikasi-aplikasi basis data yang diketahui dan transaksi-transaksi yang mungkin.

Fase perancangan basis data secara konseptual mempunyai 2 aktifitas paralel :

1. Perancangan skema konseptual :

menguji kebutuhan-kebutuhan data dari suatu basis data yang merupakan hasil dari fase 1, dan menghasilkan sebuah conceptual database schema pada DBMS-independent model data tingkat tinggi seperti EER (enhanced entity relationship) model.

Skema ini dapat dihasilkan dengan menggabungkan bermacam-macam kebutuhan pemakai dan secara langsung membuat skema basis data atau dengan merancang skema-skema yang terpisah dari kebutuhan tiap-tiap pemakai dan kemudian menggabungkan skema-skema tsb. Model data yang digunakan pada perancangan skema konseptual adalah DBMS-independent, dan langkah selanjutnya adalah memilih sebuah DBMS untuk melaksanakan rancangan tsb.

2. Perancangan transaksi :

menguji aplikasi-aplikasi basis data dimana kebutuhan-kebutuhannya telah dianalisa pada fase 1, dan menghasilkan perincian transaksi-transaksi ini. Kegunaan fase ini yang diproses secara paralel bersama fase perancangan skema konseptual adalah untuk merancang karakteristik dari transaksi-transaksi basis data yang telah diketahui pada suatu DBMS-independent. Transaksi-transaksi ini akan digunakan untuk memproses dan memanipulasi basis data suatu saat dimana basis data tsb dilaksanakan.

Fase 3 : Pemilihan DBMS

Pemilihan basis data di tentukan oleh beberapa faktor, diantaranya : faktor teknik, ekonomi, dan politik organisasi. Karena pada intinya zaman sekarang, kebanyakan DBMS digunakan dalam bidang-bidang tersebut. Maka sangat wajarlah apabila kita menggunkan factor teknik sebagai salah satu point penilaian dalam pemilihan DBMS

Contoh faktor teknik :

keberadaan DBMS dalam menjalankan tugasnya seperti jenis-jenis DBMS (relational, network, hierarchical, dll), struktur penyimpanan, dan jalur akses yang mendukung DBMS, pemakai, dll.

Faktor-faktor ekonomi dan organisasi yang mempengaruhi satu sama lain dalam pemilihan DBMS :

1. Struktur data

Jika data yang disimpan dalam basis data mengikuti struktur hirarki, maka suatu jenis hirarki dari DBMS harus dipikirkan. Karena hiraki yang semabarangan hanya akan membuat DB yang kita bangun menjadi berantakan, dan menghasilkan tingkat kesalahan yang relative besar.

2. Personal yang telah terbiasa dengan suatu sistem

Jika staf programmer dalam suatu organisasi sudah terbiasa dengan suatu DBMS, maka hal ini dapat mengurangi biaya latihan dan waktu belajar. Sebagaimana kita tahu apabila suatu organisasi menggunakan berbagai macam Hal inilah yang membuat biaya pengeluar suatu organisasi semakin besar, padahal yang diinginkan dengan adanya DBMS adalah turunnya biaya pengeluaran suatu organisasi.

3. Tersedianya layanan penjual

Keberadaan fasilitas pelayanan penjual sangat dibutuhkan untuk membantu memecahkan beberapa masalah system.

Fase 4 : Perancangan basis data secara logika (pemetaan model data)

Fase selanjutnya dari perancangan basis data adalah membuat sebuah skema konseptual dan skema eksternal pada model data dari DBMS yang terpilih. Fase ini dilakukan oleh pemetaan skema konseptual dan skema eksternal yang dihasilkan pada fase 2. Pada fase ini, skema konseptual ditransformasikan dari model data tingkat tinggi yang digunakan pada fase 2 ke dalam model data dari DBMS yang dipilih pada fase 3.

Pemetaannya dapat diproses dalam 2 tingkat :

1. Pemetaan system-independent :

pemetaan ke dalam model data DBMS dengan tidak mempertimbangkan karakteristik atau hal-hal yang khusus yang berlaku pada implementasi DBMS dari model data tsb.

2. Penyesuaian skema ke DBMS yang spesifik :

mengatur skema yang dihasilkan pada langkah 1 untuk disesuaikan pada implementasi yang khusus di masa yang akan datang dari suatu model data yang digunakan pada DBMS yang dipilih.

Hasil dari fase ini memakai perintah-perintah DDL dalam bahasa DBMS yang dipilih yang menentukan tingkat skema konseptual dan eksternal dari sistem basis data. Tetapi dalam beberapa hal, perintah-perintah DDL memasukkan parameter-parameter rancangan fisik sehingga DDL yang lengkap harus menunggu sampai fase perancangan basis data secara fisik telah lengkap.

Fase ini dapat dimulai setelah pemilihan sebuah implementasi model data sambil menunggu DBMS yang spesifik yang akan dipilih. Contoh : jika memutuskan untuk menggunakan beberapa relational DBMS tetapi belum memutuskan suatu relasi yang utama. Rancangan dari skema eksternal untuk aplikasi-aplikasi yang spesifik seringkali sudah selesai selama proses ini.

Fase 5 : Perancangan basis data secara fisik

Perancangan basis data secara fisik merupakan proses pemilihan struktur-struktur penyimpanan dan jalur-jalur akses pada file-file basis data untuk mencapai penampilan yang terbaik pada bermacam-macam aplikasi.

Selama fase ini, dirancang spesifikasi-spesifikasi untuk basis data yang disimpan yang berhubungan dengan struktur-struktur penyimpanan fisik, penempatan record dan jalur akses. Berhubungan dengan internal schema (pada istilah 3 level arsitektur DBMS).

Beberapa petunjuk dalam pemilihan perancangan basis data secara fisik :

1. Response time :

waktu yang telah berlalu dari suatu transaksi basis data yang diajukan untuk menjalankan suatu tanggapan. Pengaruh utama pada response time adalah di bawah pengawasan DBMS yaitu : waktu akses basis data untuk data item yang ditunjuk oleh suatu transaksi. Response time juga dipengaruhi oleh beberapa faktor yang tidak berada di bawah pengawasan DBMS, seperti penjadwalan sistem operasi atau penundaan komunikasi.

2. Space utility :

jumlah ruang penyimpanan yang digunakan oleh file-file basis data dan struktur-struktur jalur akses.

3. Transaction throughput :

rata-rata jumlah transaksi yang dapat diproses per menit oleh sistem basis data, dan merupakan parameter kritis dari sistem transaksi (misal : digunakan pada pemesanan tempat di pesawat, bank, dll). Hasil dari fase ini adalah penentual awal dari struktur penyimpanan dan jalur akses untuk file-file basis data.

Fase 6 : Implementasi sistem basis data

Setelah perancangan secara logika dan secara fisik lengkap, kita dapat melaksanakan sistem basis data. Perintah-perintah dalam DDL (data definition language) dan SDL (storage definition language) dari DBMS yang dipilih, dihimpun dan digunakan untuk membuat skema basis data dan file-file basis data (yang kosong). Sekarang basis data tersebut dimuat (disatukan) dengan datanya.

Jika data harus dirubah dari sistem komputer sebelumnya, perubahan-perubahan yang rutin mungkin diperlukan untuk format ulang datanya yang kemudian dimasukkan ke basis data yang baru. Transaksi-transaksi basis data sekarang harus dilaksanakan oleh para programmmer aplikasi.

Spesifikasi secara konseptual diuji dan dihubungkan dengan kode program dengan perintah-perintah dari embedded DML yang telah ditulis dan diuji. Suatu saat transaksi-transaksi tsb telah siap dan data telah dimasukkan ke dalam basis data, maka fase perancangan dan implementasi telah selesai, dan kemudian fase operasional dari sistem basis data dimulai.

Studi Kasus

tugas teori bahasa dan otomata

TEORI BAHASA DAN AUTOMATA

PENGENALAN BAHASA DAN AUTOMATA

KELOMPOK 1

KELAS 3IA08

ANGGOTA :

Abdullah Omar (50407006)

Budi Erlangga (50407262)

Devi Triwulandari (50407255)

Karina Adriani (50407487)

Nur Endah Sari (50407632)

UNIVERSITAS GUNADARMA

2010

TEORI BAHASA DAN AUTOMATA

TEORI BAHASA

Teori bahasa membicarakan bahasa formal (formal language), terutama untuk kepentingan perancangan kompilator (compiler) dan pemroses naskah (text processor). Bahasa formal adalah kumpulan kalimat. Semua kalimat dalam sebuah bahasa dibangkitkan oleh sebuah tata bahasa (grammar) yang sama. Sebuah bahasa formal bisa dibangkitkan oleh dua atau lebih tata bahasa berbeda. Dikatakan bahasa formal karena grammar diciptakan mendahului pembangkitan setiap kalimatnya. Tata bahasa (grammar) adalah kaidah/aturan pembentukan kata/kalimat. Pada pembahasannya, bahasa formal hanya disebut bahasa saja.

Bahasa dalam bentuk tulisan terdiri atas symbol-simbol satuan yang jika dikombinasikan akan mempunyai arti yang berbeda. Simbol-simbol yang biasa dipergunakan dalam sebuah bahasa terbatas jumlahnya, yang membentuk sebuah himpunan dan disebut sebagai abjad/alphabet. Namun kadangkala digunakan istilah karakter yang artinya sama dengan symbol. Deretan dari karakter atau symbol ini membentuk string. Dan himpunan dari semua string yang dibentuk dari suatu abjad ini didefinisikan sebagai bahasa.

Karena bahasa adalah sebuah himpunan dari string, maka untuk mendefinisikan suatu bahasa bisa dilakukan dengan menuliskan semua string yang menjadi anggotanya. Tata Bahasa G = (T,N,S,P), di mana

• T adalah himpunan berhingga simbol-simbol terminal

• N adalah himpunan berhingga simbol-simbol non terminal

• S adalah simbol awal, S ( N

• P adalah himpunan berhingga aturan produksi yang setiap elemennya berbentuk * + ,,

*, , ( (T U N)+, * harus berisi minimal 1 simbol non terminal

Sentential form adalah semua string yang dapat diturunkan dari simbol awal S dengan

menggunakan aturan produksi P. Kalimat (sentence) adalah sentential form yang tidak

mengandung simbol non terminal. Bahasa yang dihasilkan dari G dinotasikan dengan

L(G), yaitu himpunan kalimat yang dapat diturunkan dari S dengan menggunakan P.

AUTOMATA

Automata berasal dari bahasa Yunani automatos, yang berarti sesuatu yang bekerja secara otomatis (mesin). Istilah automata merupakan bentuk tunggal, sedangkan bentuk jamaknya adalah automaton. Teori automata adalah teori tentang mesin abstrak yang bekerja secara sekuensial yang menerima dan mengeluarkan output dalam bentuk diskrit.

Pengertian mesin bukan hanya mesin elektronis/mekanis saja melainkan segala sesuatu (termasuk perangkat lunak) yang memenuhi ketiga ciri di atas. Penggunaan automata pada perangkat lunak terutama pada pembuatan kompiler bahasa pemrograman. Secara garis besar ada dua fungsi automata dalam hubungannya dengan bahasa, yaitu :

· fungsi automata sebagai pengenal (RECOGNIZER) string-string dari suatu bahasa, dalam hal ini bahasa sebagai masukan dari automata

· fungsi automata sebagai pembangkit (GENERATOR) string-string dari suatu bahasa, dalam hal ini bahasa sebagai keluaran dari automata

Untuk mengenali string-string dari suatu bahasa, akan dimodelkan sebuah automaton

yang memiliki komponen sebagai berikut :

- pita masukan, yang menyimpan string masukan yang akan dikenali;

- kepala pita (tape head), untuk membaca/menulis ke pita masukan;

- Finite State Controller (FSC), yang berisi status-status dan aturan-aturan yang

mengatur langkah yang dilakukan oleh automaton berdasarkan status setiap saat

dan simbol masukan yang sedang dibaca oleh kepala pita;

- pengingat (memory), untuk tempat penyimpanan dan pemrosesan sementara

Automaton pengenal, setelah membaca string masukan dan melakukan langkahlangkah

pemrosesan yang diperlukan, akan mengeluarkan keputusan apakah

string tersebut dikenali atau tidak.

- Konfigurasi adalah suatu mekanisme untuk menggambarkan keadaan suatu mesin

pengenal , yang terdiri atas :

_ status FSC

_ isi pita masukan dan posisi kepala pita

_ isi pengingat

Mesin pengenal bersifat deterministik bila dalam setiap konfigurasi, hanya ada satu kemungkinan yang dapat dilakukan mesin, jika tidak mesin pengenal bersifat nondeterministik.

Sejarah Otomata dan Teori Bahasa

Otomata bermula sebelum komputer ada pada teori di bidang sistem logika matematika atau formal, ilmuwan David Hilbert telah mencoba menciptakan algoritma umum untuk pembuktian (seluruh) persoalan matematika secara otomatis yaitu mampu menentukan salah benarnya sembarang prosisi matematika.

Tahun 1931, Kurt GÖdel mempublikasikan teori ketidaklengkapan dimana membuktikan prosedur/algoritma yang dikehendaki David Hilbert tersebut tidak akan pernah ada.

GÖdel membangun rumus di kalkulus predikat yang diterapkan pada bilangan bulat yang memiliki pernyataan-pernyataan definisi yang tidak dapat dibuktikan maupun dibantah di dalam sistem logika yang mungkin dibangun manusia.

Formalisasi argumen teorema ketidaklengkapan GÖdel ini berikut penjelasan dan formalisasi selanjutnya dari prosedur efektif secara intuisi merupakan salah satu pencapaian intelektual terbesar abad 20, yaitu abad dimana formalisasi berkembang semarak.

Pengembangan teori otomata, komputasi dan teori bahasa berikutnya difasilitasi perkembangan bidang psyco-linguistic. Bidang psyco-linguistic berupaya menjawab pertanyan-pertanyan berikut:

- Apakah bahasa secara umum?

- Bagaimana manusia mengembangkan bahasa?

- Bagaimana manusia memahami bahasa?

- Bagaimana manusia mengajarkan bahasa ke anak-anaknya?

- Apa gagasan-gagasan yang dapat dinyatakan dan bagaimana caranya?

- Bagaimana manusia membangun kalimat-kalimat dari gagasan-gagasan yang berada di pikirannya?

Sekitar tahun 1950-an, Noam Chomsky menciptakan model matematika sebagai sarana untuk mendeskripsikan bahasa serta menjawab pertanyaan-pertanyaan di atas. Saat ini dimulai pendalaman bidang bahasa komputer.

Perbedaan antara bahasa komputer dan bahasa manusia adalah sampai sekarang belum diketahuinya bagaimana cara manusia mengartikan bahasa, sementara dengan pasti dapat mengartikan bahasa pada komputer.

Noam Chomsky mengemukakan perangkat format disebut grammar untuk memodelkan properti-properti bahasa.

Tata bahasa (grammer) bisa didefinisikan secara, formal sebagai kumpulan dari himpunan?himpunan variabel, simbol?simbol, terminal, simbol awal, yang dibatasi oleh aturan?aturan produksi. Tingkat bahasa dapat digolongkan menjadi empat yaitu :

1.Bahasa : Regular type 3

Mesin otomata : Finite State Otomata (FSA) meliputi deterministic finite automata dan non deterministic finite automata

Batasan aturan produksi : adalah sebuah simbol variabel maksimal memiliki sebuah simbol variabel yang bila terletak di posisi paling kanan.

2.Bahasa : Bebas konteks/context free /type 2

Mesin otomata : Push down automata (PDA)

Batasan aturan produksi : Berupa sebuah simbol variabel.

3.Bahasa : Context sensitive/type 1

Mesin otomata : Linier bounded automata

Batasan aturan produksi :

4.Bahasa : Unrestricted /phase /natural language/type 0

Mesin otomata : Mesin turing

Batasan aturan produksi : Tidak ada batasan

Semua aturan produksi dinyatakan dalam bentuk “” dimana

- : simbol?simbol pada ruas kiri aturan produksi

- : simbol?simbol pada ruas kanan

Simbol?simbol tersebut bisa berupa simbol terminal atau non terminal/ variabel.

Keterangan :

Simbol terminal biasanya dinyatakan dengan huruf kecil, misal 'a ', ‘b’, ‘c’.(tidak bisa diturunkan lagi).

Simbol non terminal dinyatakan dengan huruf besar, misal ‘A’, ‘B’, ‘C’.(masih bisa diturunkan).

Dengan menerapkan aturan produksi, suatu tata bahasa bisa menghasilkan string. Himpunan semua string tersebut adalah bahasa yang didefinisikan oleh tata bahasa tersebut.

Reguler

Pada bahasa reguler, batasannya bertambah dengan ruas kanan maksimal memiliki sebuah simbol variabel yang terletak di paling kanan. Artinya bisa memiliki simbol terminal saja dalam jumlah tidak dibatasi, tetapi bla terdapat simbol variabel tersebut hanya bejumlah satu (1) dan terletak di posisi paling kanan. Misal :

Bentuk normal chomsky / chomsky normal form (CNF ) merupakan salah satu bentuk normal yang sangat berguna untuk tata bahasa bebas konteks ( CFG ). Bentuk normal chomsky dapat di buat dari tata bahasa bebas konteks yang telah mengalami penyederhanaan yaitu penghilangan produksi useless, unit, dan ? . dengan kata lain, suatu tata bahasa bebas konteks dapat dibuat menjadi bentuk normal chomsky dengan syarat :

Tidak memiliki produksi useless

Tidak memiliki produksi unit

Tidak memiliki ?

Langkah?langkah pembentukan bentuk normal chomsky secara umum:

Biarkan aturan produksi yang sudah dalam bentuk normal Chomsky.

Lakukan penggantian aturan produksi yang ruas kanannya mermiat simbol terminal dan panjang ruas kanan > 1

Lakukan penggantian aturan produksi yang ruas kanannya mernuat >2 simbol variabel

Penggantian?penggantian tersebut bisa dilakukan berkali?kali sampai akhirnya semua aturan produksi dalam bentuk normal chomsky

Selama dilakukan penggantian, kemungkinan kita akan memperoleh aturan?aturan produksi baru, dan juga memunculkan simbol?simbol variabel baru.

Free Context

Bahasa bebas konteks menjadi dasar dalam pembentukan suatu proses analisis sintaksis. Pada bahasa bebas konteks, batasannya bertambah lagi dengan ruas kiri haruslah tepat satu symbol variable.

Contoh: B ? CdeFg ; D ? BcDe

Sensiteve Context

Pada bahasa context sensitive, panjang string pada ruas kiri panjang ruas kanan ( )

Contoh : Abc ? Def ; CD ? eF

Batasan context sensitive biasanya turut digunakan dalam proses analitis semantik pada tahapan kompilasi.

Unrestricted /phase /natural language

Bahasa manusia / bahasa alami termasuk ke dalam grammer (tata bahasa) type 0 /unrestricked, di mana tidak ada batasan pada aturan produksinya.

Contoh : Abc ? De

BEBERAPA PENGERTIAN DASAR

· Simbol adalah sebuah entitas abstrak (seperti halnya pengertian titik dalam geometri). Sebuah huruf atau sebuah angka adalah contoh simbol.

· String adalah deretan terbatas (finite) simbol-simbol. Sebagai contoh, jika a, b, dan c adalah tiga buah simbol maka abcb adalah sebuah string yang dibangun dari ketiga simbol tersebut.

· Jika w adalah sebuah string maka panjang string dinyatakan sebagai |w| dan didefinisikan sebagai cacahan (banyaknya) simbol yang menyusun string tersebut. Sebagai contoh, jika w = abcb maka |w|= 4.

· String hampa adalah sebuah string dengan nol buah simbol. String hampa dinyatakan dengan simbol ε (atau ^) sehingga |ε|= 0. String hampa dapat dipandang sebagai simbol hampa karena keduanya tersusun dari nol buah simbol.

· Alfabet adalah hinpunan hingga (finite set) simbol-simbol

OPERASI DASAR STRING

Diberikan dua string : x = abc, dan y = 123

· Prefik string w adalah string yang dihasilkan dari string w dengan menghilangkan nol atau lebih simbol-simbol paling belakang dari string w tersebut.

Contoh : abc, ab, a, dan ε adalah semua Prefix(x)

· ProperPrefix string w adalah string yang dihasilkan dari string w dengan menghilangkan satu atau lebih simbol-simbol paling belakang dari string w tersebut.

Contoh : ab, a, dan ε adalah semua ProperPrefix(x)

· Postfix (atau Sufix) string w adalah string yang dihasilkan dari string w dengan menghilangkan nol atau lebih simbol-simbol paling depan dari string w tersebut.

Contoh : abc, bc, c, dan ε adalah semua Postfix(x)

· ProperPostfix (atau PoperSufix) string w adalah string yang dihasilkan dari string w dengan menghilangkan satu atau lebih simbol-simbol paling depan dari string w tersebut.

Contoh : bc, c, dan ε adalah semua ProperPostfix(x)

· Head string w adalah simbol paling depan dari string w.

Contoh : a adalah Head(x)

· Tail string w adalah string yang dihasilkan dari string w dengan menghilangkan simbol paling depan dari string w tersebut.

Contoh : bc adalah Tail(x)

· Substring string w adalah string yang dihasilkan dari string w dengan menghilangkan nol atau lebih simbol-simbol paling depan dan/atau simbol-simbol paling belakang dari string w tersebut.

Contoh : abc, ab, bc, a, b, c, dan ε adalah semua Substring(x)

· ProperSubstring string w adalah string yang dihasilkan dari string w dengan menghilangkan satu atau lebih simbol-simbol paling depan dan/atau simbolsimbol paling belakang dari string w tersebut.

Contoh : ab, bc, a, b, c, dan ε adalah semua Substring(x)

· Subsequence string w adalah string yang dihasilkan dari string w dengan menghilangkan nol atau lebih simbol-simbol dari string w tersebut.

Contoh : abc, ab, bc, ac, a, b, c, dan ε adalah semua Subsequence(x)

· ProperSubsequence string w adalah string yang dihasilkan dari string w dengan menghilangkan satu atau lebih simbol-simbol dari string w tersebut.

Contoh : ab, bc, ac, a, b, c, dan ε adalah semua Subsequence(x)

· Concatenation adalah penyambungan dua buah string. Operator concatenation adalah concate atau tanpa lambang apapun.

Contoh : concate(xy) = xy = abc123

· Alternation adalah pilihan satu di antara dua buah string. Operator alternation adalah alternate atau | |.

Contoh : alternate(xy) = x|y = abc atau 123

· Kleene Closure : x* = ε|x|xx|xxx|… = ε|x|x 2 |x 3 |…

Positive Closure : x + = x|xx|xxx|… = x|x 2 |x 3 |…

SIFAT OPERASI DASAR STRING

· Tidak selalu berlaku : x = Prefix(x)Postfix(x)

· Selalu berlaku : x = Head(x)Tail(x)

· Tidak selalu berlaku : Prefix(x) = Postfix(x) atau Prefix(x) ≠ Postfix(x)

· Selalu berlaku : ProperPrefix(x) ≠ ProperPostfix(x)

· Selalu berlaku : Head(x) ≠ Tail(x)

· Setiap Prefix(x), ProperPrefix(x), Postfix(x), ProperPostfix(x), Head(x), dan

Tail(x) adalah Substring(x), tetapi tidak sebaliknya

· Setiap Substring(x) adalah Subsequence(x), tetapi tidak sebaliknya

· Dua sifat aljabar concatenation :

♦ Operasi concatenation bersifat asosiatif : x(yz) = (xy)z

♦ Elemen identitas operasi concatenation adalah ε : εx = xε = x

· Tiga sifat aljabar alternation :

♦ Operasi alternation bersifat komutatif : x|y = y|x

♦ Operasi alternation bersifat asosiatif : x|(y|z) = (x|y)|z

♦ Elemen identitas operasi alternation adalah dirinya sendiri : x|x = x

· Sifat distributif concatenation terhadap alternation : x (y|z) = xy|xz

· Beberapa kesamaan :

♦ Kesamaan ke-1 : (x*)* = (x*)

♦ Kesamaan ke-2 : ε|x + = x + |ε = x*

♦ Kesamaan ke-3 : (x|y)* = ε|x|y|xx|yy|xy|yx|… = semua string yang

merupakan concatenation dari nol atau lebih x, y, atau keduanya.