Rentetan

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 

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 

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 

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 …

Bahasa formal