Prof. Dra. Kiki Ariyanti Sugeng, M.Si., Ph.D.

Video ini membahas konsep rekursif dalam pembentukan string dengan concatenation. Langkah dasarnya dimulai dengan string kosong lambda, kemudian secara rekursif menggabungkan string dari alfabet yang didefinisikan. Proses ini menghasilkan kombinasi string berdasarkan alfabet yang tersedia, contohnya dari 0 dan 1. Dengan pendekatan rekursif, kita dapat membangun string dengan panjang yang semakin bertambah, seperti panjang 2 dan 3. Kombinasi string juga dapat dilakukan dengan cara membalik urutan, memberikan fleksibilitas dalam pembentukan string. Proses ini dapat diterapkan untuk memperoleh string dengan panjang yang lebih dari 3.

Ada lagi yang kita bisa bangun secara rekursif, di sini kita bicarakan string.

Kalau kita punya sigma bintang itu himpunan string di atas alfabet sigma yang didefinisikan secara rekursif,

misalnya langkah dasarnya adalah lambda itu anggota sigma bintang,

di mana si lambda ini adalah string kosong yang tidak mengandung simbol apapun.

Langkah rekursifnya adalah kalau kita punya w anggota sigma bintang dan x anggota sigma,

jadi yang tadi alfabetnya, kemudian kita gabungkan si wx itu akan ada di sigma bintang.

Jadi misalnya kita punya sigmanya adalah himpunan 0,1, jadi alfabetnya cuma 0 dan 1.

Kemudian sigma bintang itu himpunan semua string bit di sini,

yang pertama adalah si lambda yang ditentukan dalam langkah dasar,

berarti si lambda tadi kan string kosong, jadi kita mulai dari string kosong,

kemudian kita ambil elemen dari si sigmanya, jadi nanti kita akan dapat pertama 0 ditambah yang string kosong,

kita dapat 0, bukan ditambah dalam hal ini tapi digabungkan, jadi nanti kita akan dapat 0,

kemudian dari 1 kita akan dapat 1, itu hampir sama dengan sebelumnya,

tapi kita dalam bentuk string dan juga cara menggabungkannya bukan di jumlah atau di operasikan seperti yang lalu,

tapi kita tempel gitu ya, concatenation, jadi kita 0 dengan 0 kita akan dapatkan 0,0.

Kemudian yang berikutnya lagi kombinasi dari 0,1 kita dapat string 0,1, kemudian 1 sama 1 kita dapat 1,1.

Jadi kita punya string dengan panjang 2 di sini.

Dengan langkah rekursif kita akan bisa membangun string dengan nanti panjang 3, 0,0 dengan 0 kita punya 0,0,

kemudian 0,0 dengan 1 kita punya 0,0,1, 0,1 dengan 0 kita punya 0,1,0, dengan 1 kita punya 0,1,1,

kemudian 1,1 kita punya 1,1,0, kemudian 1,1,1, ini kan menyambungnya dari 0,1-nya di sebelah kanan,

kita juga bisa membalik gitu ya, jadi misalnya 1,1 dengan 0 tadi kan 1,1,0,

tapi kalau kita balik urutannya kita nanti akan dapat 0,1,1 juga.

Jadi bisa dalam 2 bentuk, kita membentuknya apakah mau ditambah di belakang atau ditambah dari depan.

Jadi kombinasinya nanti kita akan mendapatkan string dengan panjang 1, string panjang 2, dengan string panjang 3.

Langkah berikutnya lagi kita akan dapat string yang panjang yang lebih dari 4, 5, 6 dan seterusnya.