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 $s$ ditulis $|s|$.

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

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

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

$\Sigma ^{*}=\bigcup _{n\in \mathbb {N} }\Sigma ^{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 $s$ dan $t$ dalam Σ*, penjeraitan $s$ dan $t$ ialah jujukan aksara dalam $s$ dan diikuti dengan jujukan aksara dalam $t$, dan ditulis $st$. Sebagai contoh, jika Σ = {a, b, …, z}, $s$ = la, dan $t$ = gu, maka $st$ = lagu dan $ts$ = gula.

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

Suatu rentetan $s$ dipanggil subrentetan atau faktor bagi rentetan $t$ jika wujud rentetan (termasuk rentetan kosong) $u$ dan $v$ sebegitu rupa sehinggakan $t=usv$. 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 …