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 …