Teori bahasa dan otomata 1
Download as PPTX, PDF0 likes1,733 views
Teori bahasa dan otomata membahas model mesin komputer menggunakan model matematika seperti otomata dan tata bahasa formal. Konsep dasar meliputi simbol, string, bahasa, pohon sintaks, dan derivasi untuk membentuk kalimat dalam bahasa.
More Related Content
Similar to Teori bahasa dan otomata 1 (20)
Teori bahasa dan otomata 1
- 1. 1 Teori Bahasa dan Otomata 1 doktafia 10-Mar-2012
- 2. 2 doktafia 10-Mar-2012 Pendahuluan (1/3) • Ilmu komputer memiliki dua komponen utama : ▫ Model dan gagasan mendasar mengenai komputer ▫ Teknik rekayasa untuk perancangan sistem komputer meliputi hardware dan software. • Teori bahasa & otomata termasuk dalam bagian pertama yang diterapkan pada perancangan digital, pembuatan bahasa pemograman, dan kompilator. • Teori otomata mempelajari model mesin komputer menggunakan model matematika.
- 3. 3 doktafia 10-Mar-2012 Pendahuluan (2/3) • Teori otomata merupakan kajian mengenai perangkat komputasi abstrak, atau bisa dikatakan ‘’mesin abstrak’’ • Otomata adalah mesin abstrak yang dapat mengenali (recognize), menerima (accept), atau membangkitkan (generate) sebuah kalimat dalam bahasa tertentu • Pada awalnya otomata ditujukan untuk memodelkan fungsi otak, tetapi secara ekstrim tujuan tersebut akhirnya berubah untuk berbagai keperluan lainnya. • Pada tahun 1950-an, pakar bahasa N. Chomsky mulai mempelajari studi tentang tata bahasa formal (formal grammar). Secara langsung tata bahasa tersebut tidak terkait dengan mesin, tetapi memiliki hubungan erat dengan otomata abstrak dan saat ini menjadi dasar bagi sejumlah komponen perangkat lunak, termasuk bagian-bagian dari kompiler.
- 4. 4 doktafia 10-Mar-2012 Pendahuluan (3/3) • Grammar memiliki manfaat sangat besar di ilmu informatika/komputer untuk mendeskripsikan dan mendefinisikan sintaks bahasa pemrograman dan bahasa-bahasa formal yang lain. • Grammar diterapkan pada perancangan kompilator dan bidang-bidang lain dalam ilmu komputer.
- 5. 5 doktafia 10-Mar-2012 Beberapa Pengertian Dasar • Simbol adalah sebuah entitas abstrak. Sebuah huruf atau angka adalah contoh simbol. • String/untai/ adalah deretan terbatas (finite) simbol-simbol ▫ Ex : jika a,b,c adalah simbol, maka abcb adalah string yang dibangun dari ketiga simbol tersebut. • Jika w adalah sebuah string, maka panjang string dinyatakan sebagai |w|, yang didefinisikan sebagai banyak simbol yang menyusun string tersebut. ▫ Ex : jika w = abcb maka |w| = 4 • String hampa adalah sebuah string dengan nol buah simbol. String hampa dinyatakan dengan simbol ε atau ^ sehingga | ε | = 0 • Bahasa (language) adalah kumpulan dari untai-untai atau string
- 6. 6 doktafia 10-Mar-2012 Konsep Dasar (1/4) Si Kucing Kecil Menendang Bola Besar
- 7. 7 doktafia 10-Mar-2012 Konsep Dasar (2/4) • Pohon sintaks dapat dituliskan dalam bentuk sebuah produksi : 1. <Kalimat> ïƒ <Subjek><Predikat> 2. <Subjek> ïƒ <Kata Sandang><Kata Benda><Kata Keadaan> 3. <Predikat> ïƒ <Kata Kerja><Objek> 4. <Objek> ïƒ <Kata Benda><Kata Keadaan> 5. <Kata Sandang> ïƒ Si 6. <Kata Benda> ïƒ Kucing | Bola 7. <Kata Keadaan> ïƒ Kecil | Besar 8. <Kata Kerja> ïƒ Menendang • Untai terminal dapat dibentuk dengan melakukan sederetan produksi menggunakan produksi yang ada. Proses ini disebut dengan Derivasi.
- 8. 8 doktafia 10-Mar-2012 Konsep Dasar (3/4) Si Kucing Kecil Menendang Bola Besar Derivasi untuk untai di atas adalah : <Kalimat> ïƒ <Subjek><Predikat> ïƒ <Kata Sandang><Kata Benda><Kata Keadaan><Predikat> ïƒ <Kata Sandang><Kata Benda><Kata Keadaan><Kata Kerja> <Objek> ïƒ <Kata Sandang><Kata Benda><Kata Keadaan><Kata Kerja> <Kata Benda><Kata Keadaan> ïƒ Si Kucing Kecil Menendang Bola Besar Untai lain yang bisa terbentuk : Si Bola Kecil Menendang Kucing Besar Si Kucing Besar Menendang Bola Kecil, dll.
- 9. 9 doktafia 10-Mar-2012 Konsep Dasar (4/4) Contoh berikut adalah contoh bagaimana membangun operand yang absah dalam suatu bahasa pemograman. Kita definisikan himpunan 8 produksi dengan simbol Start adalah <OPERAND> sebagai berikut : 1. <OPERAND> ïƒ <ID> | <INTEGER> 2. <ID> ïƒ <LETTER><LIST> 3. <LETTER> ïƒ x | y | z 4. <LIST> ïƒ <LETTER><LIST> | <DIGIT><LIST> | ^ 5. <DIGIT> ïƒ 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 6. <INTEGER> ïƒ <SIGN><DIGIT><DIT> 7. <SIGN> ïƒ + | - 8. <DIT> ïƒ <DIGIT><DIT> | ^ <OPERAND> ïƒ <ID> ïƒ <LETTER><LIST> ïƒ y <LIST> ïƒ y <DIGIT><LIST> Derivasinya ïƒ y7 <LIST> ïƒ y7^ atau y7
- 10. 10 doktafia 10-Mar-2012 Latihan • Apakah untai terminal berikut absah sebagai operand bahasa pemograman, kalau absah tentukan derivasinya ▫ 4xy2 ▫ x2y ▫ -21x ▫ xxb ▫ +1230 ▫ x123 ▫ x-y+2 ▫ x1x2x3x ▫ xxxyyy