Rentetan

jenis data yang mengandungi aksara yang berturutan

Dalam teori bahasa formal dan sains komputer, rentetan ialah jujukan simbol yang yang diambil daripada suatu set yang dipanggil abjad.

Dalam konteks pengaturcaraan komputer, rentetan merujuk kepada jujukan aksara. Umumnya rentetan dipandang sebagai satu jenis data yang mengandungi jujukan bait mengikut pengekodan aksara tertentu.

Teori formal sunting

Katakan abjad Σ ialah suatu set terhingga bukan kosong. Unsur-unsur dalam Σ dipanggil simbol atau aksara. Suatu rentetan terhadap Σ ialah sebarang jujukan terhingga bagi aksara-aksara dalam Σ. Sebagai contoh, jika Σ = {0, 1}, maka 0101 ialah satu rentetan terhadap Σ.

Panjang bagi suatu rentetan ialah integer bukan negatif yang mewakili bilangan aksara yang terkandung dalam rentetan itu. Panjang bagi rentetan   ditulis  .

Rentetan kosong ialah suatu rentetan unik terhadap Σ dengan panjang 0, dan diberi tatatanda ε atau λ.

Set bagi semua rentetan terhadap Σ dengan panjang   ditulis Σn. Sebagai contoh, jika Σ = {0, 1}, maka Σ2 = {00, 01, 10, 11}. Σ0 = {ε} untuk semua abjad Σ.

Set bagi semua rentetan terhadap Σ dengan sebarang panjang ialah tutupan Kleene bagi Σ dan ditulis Σ*. Dalam sebutan Σn,

 

Sebagai contoh, jika Σ = {0, 1}, maka Σ* = {ε, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, …}. Sungguhpun Σ* tak terhingga, semua unsur dalam Σ* mempunyai panjang terhingga.

Sebarang set rentetan terhadap Σ, iaitu subset bagi Σ*, dipanggil bahasa formal terhadap Σ. Sebagai contoh, jika Σ = {0, 1}, maka set bagi semua rentetan yang mengandungi bilangan sifar ganjil ({ε, 1, 00, 11, 001, 010, 100, 111, 0000, 0011, 0101, 0110, 1001, 1010, 1100, 1111, …}) adalah suatu bahasa formal terhadap Σ.

Penjeraitan dan subrentetan sunting

Penjeraitan ialah suatu operasi dedua dalam Σ*. Untuk sebarang dua rentetan   dan   dalam Σ*, penjeraitan   dan   ialah jujukan aksara dalam   dan diikuti dengan jujukan aksara dalam  , dan ditulis  . Sebagai contoh, jika Σ = {a, b, …, z},   = la, dan   = gu, maka   = lagu dan   = gula.

Operasi penjeraitan rentetan adalah kalis sekutuan, tetapi tidak kalis tukar tertib. Rentetan kosong bertindak sebagai unsur identiti terhadap penjeraitan. Untuk semua rentetan  , ε  =  ε =  . Oleh itu, Σ* dan penjeraitan membentuk sebuah monoid, iaitu monoid bebas yang dijana oleh Σ.

Suatu rentetan   dipanggil subrentetan atau faktor bagi rentetan   jika wujud rentetan (termasuk rentetan kosong)   dan   sebegitu rupa sehinggakan  . Sebagai contoh, jalan adalah subrentetan bagi perjalanan, pejalan, dan jalanan.

Penertiban leksikografi sunting

Jika abjad Σ tertertib seluruh, tertib seluruh bagi Σ* yang dipanggil tertib leksikografi boleh ditakrifkan. Oleh kerana Σ adalah terhingga, penertiban rapi bagi Σ sentiasa boleh dilakukan dan begitu juga bagi Σ*. Sebagai contoh, jika Σ = {0, 1} dan 0 < 1, maka penertiban leksikografi bagi Σ* ialah ε < 0 < 00 < 000 < … < 011 < 0110 < … < 01111 < … < 1 < 10 < 100 < … < 101 < … < 111 …