teori bahasa dan otomata 5

Teori bahasa dan otomata 5 1. Pohon (Tree)POHON (TREE)Pohon (Tree) didefinisikan sebagai graph terhubung yang tidak mengandung sirkuit.Sedangkan Hutan (Forest) adalah graph yang tidak mengandung sirkuit. Jadi pohonadalah hutan yang terhubung.Untuk itu perlu diingat kembali bahwa :• Suatu Graf G disebut terhubung apabila untuk setiap dua simpul dari graf G selalu terdapat jalur yang menghubungkan kedua simpul tersebut.• Sirkuit atau cycle adalah suatu lintasan tertutup dengan derajat setiap simpul dua.Contoh :Sifat :Suatu Graf G adalah Pohon jika dan hanya jika terdapat satu dan hanya satu jalurdiantara setiap pasang simpul dari Graf G. 2. Pohon (Tree)Teorema :Suatu Graf G dengan n buah simpul adalah Pohon jika :(1) G terhubung dan tak mengandung sirkuit, atau(2) G tidak mengandung sirkuit dan mempunyai n - 1 buah ruas, atau(3) G mempunyai n - 1 buah ruas dan terhubungTeorema :Pohon (dan hutan) adalah berwarna 2.POHON RENTANGAN (SPANNING TREE)Suatu pohon rentangan atau spanning tree adalah suatu subgraf dari graf G yangmengandung semua simpul dari G dan merupakan suatu pohon. GRAF G SPANNING TREE n simpul n simpul m ruas n – 1 ruas Cabang (Branch) m - (n - 1) ChordContoh : Keterangan Branch ChordLogika dan Algoritma – Yuni Dwi Astuti, ST 2 3. Pohon (Tree)Contoh :Graf GSpanning tree dari graf GPOHON RENTANGAN MINIMAL (MINIMAL SPANNING TREE)Apabila G suatu Graf berbobot (Suatu Network), maka pohon rentangan minimal darigraf adalah pohon rentangan dengan jumlah bobot terkecil.Logika dan Algoritma – Yuni Dwi Astuti, ST 3 4. Pohon (Tree)Untuk mendapatkan pohon rentangan minimal dapat digunakan Algoritma berikut :SOLIN1. Urutkan ruas dari G menurut bobotnya, dari besar ke kecil.2. Lakukan penghapusan ruas berdasarkan urutan yang sudah dilakukan, dengan ketentuan bahwa penghapusan ruas tersebut tidak menyebabkan graf menjadi tidak terhubung.KRUSKAL1. Urutkan ruas dari G menurut bobotnya, dari kecil ke besar.2. Lakukan penambahan ruas berdasarkan urutan yang sudah dilakukan, dengan ketentuan bahwa penambahan ruas tersebut tidak menyebabkan adanya sirkuit.PRIM’S= Kruskal + menjaga graf tetap terhubungContoh : Total bobot = 4 + 3 + 2 + 5 + 2 + 4 + 2 + 2 + 3 = 27Logika dan Algoritma – Yuni Dwi Astuti, ST 4 5. Pohon (Tree)POHON BERAKAR (ROOTED TREE)Suatu pohon berakar R adalah suatu pohon bersama dengan suatu simpul r yangdirancang/ditunjuk sebagai akar (root) dari R.• Seperti diketahui bahwa hanya terdapat satu jalur antara r dengan simpul lain v pada pohon pohon tersebut.• Panjang jalur antara r dengan simpul v disebut level atau kedalaman simpul v.• Simpul bukan akar, yang berderajat satu disebut daun. Jalur antara suatu simpul dengan suatu daun disebut cabang (branch).Contoh :• Simpul u dikatakan mendahului simpul v jika jalur dari akar r ke v melalui u.• Dikatakan u mendahului langsung v bila u mendahului v serta simpul u dan v berdampingan.• Pada contoh di atas, a mendahului d, mendahului e, dan mendahului h.Suatu pohon berakar dapat digunakan untuk menelusuri semua kemungkinan darikejadian, dengan masing-masing kejadian dapat muncul dalam sejumlah hingga cara.Bebarapa contoh lain yang penting dari pohon berakar adalah pohon binar (binary tree)dan pohon sintaks (syntax tree) atau pohon derivasi (derivation tree).Logika dan Algoritma – Yuni Dwi Astuti, ST 5 6. Pohon (Tree)POHON BINAR (BINARY TREE)Dalam struktur data, pohon memegang peranan yang cukup penting. Struktur inibiasanya digunakan terutama untuk menyajikan data yang mengandung hubunganhierarkykal antara elemen-elemen mereka.Bentuk pohon khusus yang lebih mudah dikelola dalam komputer adalah pohonbinary. Bentuk ini merupakan bentuk pohon yang umum. Sebuah pohon binar Tdidefinisikan terdiri dari sebuah himpunan hingga elemen yang disebut simpul,sedemikian sehingga :a. T adalah hampa (disebut pohon null) ataub. T mengandung simpul R yang dipilih disebut akar (root) dari T, dan simpul sisanya membentuk 2 pohon binary T1 dan T2 yang saling lepas.Setiap simpul didalam pohon binar hanya dapat mempunyai 0, 1 atau 2 successor(turunan langsung).Untuk menyajikan pohon binar, simpul akar adalah simpul yang digambar pada bagianpaling atas. Sedangkan suksesor kiri (left successor) digambarkan sebagai garis ke kiribawah dan suksesor kanan (right successor) sebagai garis ke kanan bawah.Contoh :Logika dan Algoritma – Yuni Dwi Astuti, ST 6 7. Pohon (Tree) B adalah left successor dan C adalah right successor dari simpul A Left subtree dari root A terdiri dari simpul B, D, E, F Right subtree dari root A terdiri dari simpul C, G, H, J, K, L F adalah left successor dari simpul E L adalah right successor dari simpul J Kedalaman atau ketinggian (depth/height) dari pohon binar T adalah banyak maksimum simpul dari cabang di T. Untuk pohon binar di atas, ketinggiannya adalah 5.Pohon biner T dan T′ disebut similar jika strukturnya (bentuknya) sama.Pohon biner T dan T′ disebut salinan (copy) jika strukturnya (bentuknya) sama dannama simpulnya sama.Contoh :Gambar semua kemungkinan pohon biner yang non-similar dengan 3 simpulPOHON BINAR LENGKAPSuatu pohon binar T dikatakan lengkap bila setiap tingkatnya, kecuali mungkin tingkatyang terakhir, mempunyai semua simpul yang mungkin, yaitu 2r simpul untuk tingkatke-r, dan bila semua simpul pada tingkat terakhir muncul di bagian kiri pohon.Kedalaman atau ketinggian pohon binar lengkap T dengan n simpul : INT(2log n) + 1Logika dan Algoritma – Yuni Dwi Astuti, ST 7 8. Pohon (Tree)Contoh :POHON - 2Pohon binar T dikatakan pohon-2 atau pohon binar yang diperluas (extended binary tree)bila setiap simpul mempunyai 0 atau 2 anak.• Simpul dengan 2 anak disebut simpul internal, digambarkan sebagai lingkaran. Biasanya berfungsi sebagai operator.• Simpul dengan 0 anak disebut simpul eksternal, digambarkan sebagai segi-empat. Biasanya berfungsi sebagai operand.Contoh : Pohon-2 yang menyajikan ekspresi (a-b)/((c+d)*e)Logika dan Algoritma – Yuni Dwi Astuti, ST 8 9. Pohon (Tree)POHON SINTAKS (SYNTAX TREE)Untuk menjelaskan mengenai bahasa secara teoritis dan formal, kita lihat terlebihdahulu sebuah kalimat sehari-hari dalam bahasa Indonesia, yaitu : Si kucing kecil menendang bola besarGambar penguraian kalimat di atas membentuk struktur pohon, yang disebut pohonsintaks dari kalimat. Disini kalimat dibagi-bagi berdasar jenis dan fungsi kata. Daripelajaran bahasa Indonesia kita tahu bahwa kalimat di atas telah benar susunannya,atau telah benar tata bahasanya.Pohon sintaks dari kalimat di atas dapat dilihat sebagai berikut :Derivasi adalah proses pembentukan untai terminal dengan melakukan sederetanproduksi menggunakan himpinan produksi yang ada.Himpunan produksi dari pohon sintaks diatas adalah :1. → 2. → 3. → 4. → Logika dan Algoritma – Yuni Dwi Astuti, ST 9 10. Pohon (Tree)5. → si6. → kucing | bola7. → kecil |besar8. → menendangSoal Latihan :Lakukan derivasi terhadap untai terminal x1x2x3 dengan himpunan produksi sebagaiberikut :1. → | 2. → 3. →x|y|z4. → < LIST> | | ^5. → 0|1|2|3|4|5|6|7|8|96. → | 7. → - |+8. → |Teori bahasa dan otomata 5 1. Pohon (Tree)POHON (TREE)Pohon (Tree) didefinisikan sebagai graph terhubung yang tidak mengandung sirkuit.Sedangkan Hutan (Forest) adalah graph yang tidak mengandung sirkuit. Jadi pohonadalah hutan yang terhubung.Untuk itu perlu diingat kembali bahwa :• Suatu Graf G disebut terhubung apabila untuk setiap dua simpul dari graf G selalu terdapat jalur yang menghubungkan kedua simpul tersebut.• Sirkuit atau cycle adalah suatu lintasan tertutup dengan derajat setiap simpul dua.Contoh :Sifat :Suatu Graf G adalah Pohon jika dan hanya jika terdapat satu dan hanya satu jalurdiantara setiap pasang simpul dari Graf G. 2. Pohon (Tree)Teorema :Suatu Graf G dengan n buah simpul adalah Pohon jika :(1) G terhubung dan tak mengandung sirkuit, atau(2) G tidak mengandung sirkuit dan mempunyai n - 1 buah ruas, atau(3) G mempunyai n - 1 buah ruas dan terhubungTeorema :Pohon (dan hutan) adalah berwarna 2.POHON RENTANGAN (SPANNING TREE)Suatu pohon rentangan atau spanning tree adalah suatu subgraf dari graf G yangmengandung semua simpul dari G dan merupakan suatu pohon. GRAF G SPANNING TREE n simpul n simpul m ruas n – 1 ruas Cabang (Branch) m - (n - 1) ChordContoh : Keterangan Branch ChordLogika dan Algoritma – Yuni Dwi Astuti, ST 2 3. Pohon (Tree)Contoh :Graf GSpanning tree dari graf GPOHON RENTANGAN MINIMAL (MINIMAL SPANNING TREE)Apabila G suatu Graf berbobot (Suatu Network), maka pohon rentangan minimal darigraf adalah pohon rentangan dengan jumlah bobot terkecil.Logika dan Algoritma – Yuni Dwi Astuti, ST 3 4. Pohon (Tree)Untuk mendapatkan pohon rentangan minimal dapat digunakan Algoritma berikut :SOLIN1. Urutkan ruas dari G menurut bobotnya, dari besar ke kecil.2. Lakukan penghapusan ruas berdasarkan urutan yang sudah dilakukan, dengan ketentuan bahwa penghapusan ruas tersebut tidak menyebabkan graf menjadi tidak terhubung.KRUSKAL1. Urutkan ruas dari G menurut bobotnya, dari kecil ke besar.2. Lakukan penambahan ruas berdasarkan urutan yang sudah dilakukan, dengan ketentuan bahwa penambahan ruas tersebut tidak menyebabkan adanya sirkuit.PRIM’S= Kruskal + menjaga graf tetap terhubungContoh : Total bobot = 4 + 3 + 2 + 5 + 2 + 4 + 2 + 2 + 3 = 27Logika dan Algoritma – Yuni Dwi Astuti, ST 4 5. Pohon (Tree)POHON BERAKAR (ROOTED TREE)Suatu pohon berakar R adalah suatu pohon bersama dengan suatu simpul r yangdirancang/ditunjuk sebagai akar (root) dari R.• Seperti diketahui bahwa hanya terdapat satu jalur antara r dengan simpul lain v pada pohon pohon tersebut.• Panjang jalur antara r dengan simpul v disebut level atau kedalaman simpul v.• Simpul bukan akar, yang berderajat satu disebut daun. Jalur antara suatu simpul dengan suatu daun disebut cabang (branch).Contoh :• Simpul u dikatakan mendahului simpul v jika jalur dari akar r ke v melalui u.• Dikatakan u mendahului langsung v bila u mendahului v serta simpul u dan v berdampingan.• Pada contoh di atas, a mendahului d, mendahului e, dan mendahului h.Suatu pohon berakar dapat digunakan untuk menelusuri semua kemungkinan darikejadian, dengan masing-masing kejadian dapat muncul dalam sejumlah hingga cara.Bebarapa contoh lain yang penting dari pohon berakar adalah pohon binar (binary tree)dan pohon sintaks (syntax tree) atau pohon derivasi (derivation tree).Logika dan Algoritma – Yuni Dwi Astuti, ST 5 6. Pohon (Tree)POHON BINAR (BINARY TREE)Dalam struktur data, pohon memegang peranan yang cukup penting. Struktur inibiasanya digunakan terutama untuk menyajikan data yang mengandung hubunganhierarkykal antara elemen-elemen mereka.Bentuk pohon khusus yang lebih mudah dikelola dalam komputer adalah pohonbinary. Bentuk ini merupakan bentuk pohon yang umum. Sebuah pohon binar Tdidefinisikan terdiri dari sebuah himpunan hingga elemen yang disebut simpul,sedemikian sehingga :a. T adalah hampa (disebut pohon null) ataub. T mengandung simpul R yang dipilih disebut akar (root) dari T, dan simpul sisanya membentuk 2 pohon binary T1 dan T2 yang saling lepas.Setiap simpul didalam pohon binar hanya dapat mempunyai 0, 1 atau 2 successor(turunan langsung).Untuk menyajikan pohon binar, simpul akar adalah simpul yang digambar pada bagianpaling atas. Sedangkan suksesor kiri (left successor) digambarkan sebagai garis ke kiribawah dan suksesor kanan (right successor) sebagai garis ke kanan bawah.Contoh :Logika dan Algoritma – Yuni Dwi Astuti, ST 6 7. Pohon (Tree) B adalah left successor dan C adalah right successor dari simpul A Left subtree dari root A terdiri dari simpul B, D, E, F Right subtree dari root A terdiri dari simpul C, G, H, J, K, L F adalah left successor dari simpul E L adalah right successor dari simpul J Kedalaman atau ketinggian (depth/height) dari pohon binar T adalah banyak maksimum simpul dari cabang di T. Untuk pohon binar di atas, ketinggiannya adalah 5.Pohon biner T dan T′ disebut similar jika strukturnya (bentuknya) sama.Pohon biner T dan T′ disebut salinan (copy) jika strukturnya (bentuknya) sama dannama simpulnya sama.Contoh :Gambar semua kemungkinan pohon biner yang non-similar dengan 3 simpulPOHON BINAR LENGKAPSuatu pohon binar T dikatakan lengkap bila setiap tingkatnya, kecuali mungkin tingkatyang terakhir, mempunyai semua simpul yang mungkin, yaitu 2r simpul untuk tingkatke-r, dan bila semua simpul pada tingkat terakhir muncul di bagian kiri pohon.Kedalaman atau ketinggian pohon binar lengkap T dengan n simpul : INT(2log n) + 1Logika dan Algoritma – Yuni Dwi Astuti, ST 7 8. Pohon (Tree)Contoh :POHON - 2Pohon binar T dikatakan pohon-2 atau pohon binar yang diperluas (extended binary tree)bila setiap simpul mempunyai 0 atau 2 anak.• Simpul dengan 2 anak disebut simpul internal, digambarkan sebagai lingkaran. Biasanya berfungsi sebagai operator.• Simpul dengan 0 anak disebut simpul eksternal, digambarkan sebagai segi-empat. Biasanya berfungsi sebagai operand.Contoh : Pohon-2 yang menyajikan ekspresi (a-b)/((c+d)*e)Logika dan Algoritma – Yuni Dwi Astuti, ST 8 9. Pohon (Tree)POHON SINTAKS (SYNTAX TREE)Untuk menjelaskan mengenai bahasa secara teoritis dan formal, kita lihat terlebihdahulu sebuah kalimat sehari-hari dalam bahasa Indonesia, yaitu : Si kucing kecil menendang bola besarGambar penguraian kalimat di atas membentuk struktur pohon, yang disebut pohonsintaks dari kalimat. Disini kalimat dibagi-bagi berdasar jenis dan fungsi kata. Daripelajaran bahasa Indonesia kita tahu bahwa kalimat di atas telah benar susunannya,atau telah benar tata bahasanya.Pohon sintaks dari kalimat di atas dapat dilihat sebagai berikut :Derivasi adalah proses pembentukan untai terminal dengan melakukan sederetanproduksi menggunakan himpinan produksi yang ada.Himpunan produksi dari pohon sintaks diatas adalah :1. → 2. → 3. → 4. → Logika dan Algoritma – Yuni Dwi Astuti, ST 9 10. Pohon (Tree)5. → si6. → kucing | bola7. → kecil |besar8. → menendangSoal Latihan :Lakukan derivasi terhadap untai terminal x1x2x3 dengan himpunan produksi sebagaiberikut :1. → | 2. → 3. →x|y|z4. → < LIST> | | ^5. → 0|1|2|3|4|5|6|7|8|96. → | 7. → - |+8. → |