Lihat sumber bagi 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 <math>s</math> ditulis <math>|s|</math>.

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

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

Set bagi semua rentetan terhadap Σ dengan sebarang panjang ialah [[tutupan Kleene]] bagi Σ dan ditulis Σ*. Dalam sebutan Σ<sup>n</sup>,

:<math>\Sigma^{*} = \bigcup_{n \in \N} \Sigma^{n}</math>

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 [[nombor ganjil|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 <math>s</math> dan <math>t</math> dalam Σ*, penjeraitan <math>s</math> dan <math>t</math> ialah jujukan aksara dalam <math>s</math> dan diikuti dengan jujukan aksara dalam <math>t</math>, dan ditulis <math>st</math>. Sebagai contoh, jika Σ = {a, b, …, z}, <math>s</math> = <tt>la</tt>, dan <math>t</math> = <tt>gu</tt>, maka <math>st</math> = <tt>lagu</tt> dan <math>ts</math> = <tt>gula</tt>.

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

Suatu rentetan <math>s</math> dipanggil ''subrentetan'' atau ''faktor'' bagi rentetan <math>t</math> jika wujud rentetan (termasuk rentetan kosong) <math>u</math> dan <math>v</math> sebegitu rupa sehinggakan <math>t = usv</math>. Sebagai contoh, <tt>jalan</tt> adalah subrentetan bagi <tt>perjalanan</tt>, <tt>pejalan</tt>, dan <tt>jalanan</tt>.

=== Penertiban leksikografi ===

Jika abjad Σ ter[[tertib 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 …

[[Kategori:Bahasa formal]]