Jelaskan Teori formal dari Rentetan dalam bahasa melayu

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 Σ.