Bahasa formal

Bahasa formal ialah sejenis pengitlakan konsep bahasa yang kita kenali dalam kehidupan harian.

Konsep asas

Sebagai permulaan, kita boleh membayangkan bahasa formal seperti bahasa biasa, contohnya bahasa Melayu. Bahasa sebegini terdiri daripada apa? Bahasa terdiri daripada perkataan yang kita gabungkan pula menjadi ayat. Ayat tidak akan kita bincangkan; kita hanya berminat dengan perkataan. Perkataan pula terdiri daripada apa? Perkataan terdiri daripada huruf abjad. Oleh itu, kita mulakan dengan abjad.

Abjad ialah sebarang set yang tidak kosong. Unsur abjad dipanggil simbol. Bagi bahasa Melayu, abjadnya ialah abjad Rumi yang biasa, merangkumi huruf kecil dan huruf besar. Jika kita tidak mahu memerihalkan bahasa Melayu tetapi, misalnya, nombor, abjad kita akan mengandungi kesemua sepuluh digit. Abjad lazimnya ditandakan dengan simbol Σ.

Rentetan (dalam teori bahasa formal juga disebut perkataan) ialah jujukan terhingga simbol daripada suatu abjad Σ. Contohnya, jika kita mempunyai abjad Σ= {a,b,c,d,e,…, z}, maka jujukan “helo” atau “kucing” ialah rentetan, tetapi “kafé” bukan rentetan (abjad itu tiada huruf “é”), begitu juga “Ahmad” (tiada huruf “A”) dan “selamat pagi” (tiada ruang kosong). Panjang rentetan ialah bilangan simbol yang membentuk rentetan itu.

Perangkaian rentetan: jika kita mempunyai dua rentetan a = a₁a₂… a_n dan b = b₁b₂… b_m, perangkaian kedua-duanya menghasilkan rentetan ab = a₁a₂… a_nb₁b₂… b_m. Contohnya, perangkaian rentetan “helo” dan “kucing” menghasilkan rentetan “helokucing”. Perangkaian ditandakan sama ada dengan bulatan kecil, iaitu a ∘ b, atau tidak ditandakan langsung: kedua-dua rentetan ditulis bersebelahan tanpa simbol khas.

Rentetan kosong ditandakan dengan ε, iaitu rentetan yang panjangnya sifar. Jika kita merangkaikan rentetan a = a₁… a_n dengan rentetan kosong ε, kita memperoleh semula rentetan a. Maksudnya, a ∘ ε = a.

Tutupan abjad Σ ialah set semua rentetan yang boleh dibentuk daripada abjad Σ, termasuk rentetan kosong. Tutupan ditandakan dengan Σ^∗. Jika kita mempunyai abjad binari Σ= {0, 1}, maka

$${\mathrm{\Sigma }}^{\ast }=\{\epsilon ,0,1,00,01,10,11,000,001,\dots \}$$

Kadangkala kita juga menggunakan tutupan positif abjad, iaitu sekali lagi semua rentetan yang boleh dibentuk daripada abjad itu, kecuali rentetan kosong. Tutupan positif ditandakan dengan Σ⁺, dan Σ⁺ = Σ^∗ ∖ {ε}.

Contoh abjad

• Mari kita kembali kepada contoh bahasa Melayu. Setiap perkataan Melayu terdapat dalam tutupan abjad yang mengandungi huruf kecil dan huruf besar (serta mungkin juga tanda sempang “-”). Jika kita menambahkan ruang kosong dan tanda baca (koma, noktah, tanda seru, tanda soal, …) kepada abjad ini, tutupannya memberikan semua ayat yang boleh dibentuk dalam bahasa Melayu. Sudah tentu tutupan ini juga mengandungi ayat seperti “sadflsf kasdf kagrjewqqxker kf fkjbsjbgvbadfgsa!!!:??: ::!?:?:sdf”, yang langsung tidak bermakna.

• Jika abjad kita mengandungi semua digit Σ= {0, 1, …, 9}, tutupannya mengandungi semua nombor asli — dan beberapa rentetan lain lagi. Tutupan itu juga mengandungi nombor yang bermula dengan sifar, contohnya 00054, atau sifar sahaja, dan juga rentetan kosong, yang sudah tentu bukan nombor.

• Abjad mestilah tidak kosong, jadi abjad yang terkecil mempunyai sekurang-kurangnya satu simbol. Contohnya, bagi abjad Σ= {!} kita memperoleh tutupan Σ^∗ = {ε, !, !!, !!!, !!!!, …}, iaitu set rentetan yang mengandungi, bagi setiap n ∈ ℕ₀, rentetan yang mempunyai n tanda seru, dan tiada rentetan lain.

• Katakan Σ= {qw,c}. Abjad ini sangat ganjil kerana mengandungi rentetan qw. Tatatanda ini jarang digunakan kerana mengelirukan dan pelik, tetapi kita boleh membayangkan bahawa huruf “q” dan “w” dicantumkan sehingga membentuk satu aksara. Dengan itu, rentetan “qw” boleh dilihat sebagai simbol “qw”. Jika kita membentuk rentetan “qwcqw” daripada simbol ini, panjang rentetan itu ialah tiga — rentetan itu terdiri daripada simbol “qw”, “c” dan “qw”. Abjad seperti ini jarang ditemui, tetapi ada situasi apabila kita perlu menggunakan simbol yang terdiri daripada beberapa simbol.

Bahasa formal

Bahasa (formal) atas abjad Σ ialah sebarang subset bagi Σ^∗. Oleh itu, bagi bahasa L atas abjad Σ, L ⊆ Σ^∗. Contoh bahasa:

• Dalam bahagian sebelum ini, kita telah mentakrifkan abjad digit Σ= {0, 1, …, 9}. Tutupannya ialah semua rentetan yang terdiri daripada digit sahaja. Jika kita menambahkan peraturan bahawa rentetan tidak boleh bermula dengan sifar dan tidak boleh kosong, kita memperoleh set nombor asli ℕ. Oleh sebab ℕ ⊆ Σ^∗, ℕ ialah bahasa atas abjad Σ.

• Kepada set digit tadi kita boleh menambahkan tanda tolak “-”, jadi Σ= {0, 1, …, 9, −}. Tutupannya ialah semua rentetan yang terdiri daripada digit atau tanda tolak. Ini bermakna tutupan itu juga mengandungi rentetan seperti “12-84-”, “1-5-8” atau “-”. Bahasa integer ℤ dibentuk dengan menambahkan tiga peraturan:

  • Tanda tolak sama ada tidak muncul langsung dalam rentetan, atau muncul pada awal rentetan.
  • Digit pertama dalam rentetan tidak boleh sifar, kecuali bagi rentetan “0”.
  • Setiap rentetan mesti mengandungi sekurang-kurangnya satu digit.

  Set ini memerihalkan set integer dan merupakan subset bagi set Σ^∗ — maka set ini ialah bahasa atas abjad Σ.

• Katakan Σ= {0, 1}. Tutupannya ialah semua rentetan yang terdiri daripada sifar dan satu. Bahasa L atas abjad ini boleh ditakrifkan, misalnya, sebagai set semua rentetan yang mempunyai tepat tiga digit satu. Kita boleh juga lebih kreatif dan menetapkan bahawa bahasa L ialah set semua rentetan yang mewakili fail sah dalam format docx (fail yang dihasilkan oleh pemproses kata).

• Kita kekal dengan abjad binari Σ= {0, 1}. Setiap rentetan aksara (aksara biasa yang terdapat pada papan kekunci) boleh ditukarkan kepada bentuk binari, iaitu kepada sifar dan satu, dan sebaliknya, misalnya menggunakan jadual ASCII (atau lebih tepat lagi — jadual ASCII menukarkan aksara kepada nombor, dan nombor dalam asas sepuluh boleh ditukarkan kepada nombor dalam asas dua). Oleh itu, kita boleh mentakrifkan bahasa semua rentetan yang merupakan alamat e-mel yang sah, dan bahasa itu tetap bahasa atas abjad binari.

Perangkaian bahasa: bahasa juga boleh dirangkaikan. Takrifnya serupa dengan takrif hasil darab Cartes bagi set. Katakan kita mempunyai dua bahasa L₁ dan L₂. Perangkaian kedua-duanya, L₁ ∘ L₂, menghasilkan bahasa baharu yang ditakrifkan seperti berikut:

$$L_1\circ L_2=\{w_1\circ w_2|w_1\in L_1,w_2\in L_2\}$$

Maksudnya, kita mengambil semua rentetan daripada bahasa L₁ dan merangkaikannya dengan semua rentetan daripada bahasa L₂. Contoh: Katakan

$$\begin{array}{rcl}{L}_1& =& \{0,1\}\\ L_2& =& \{a,b,helo\}\end{array}$$

Maka:

$$\begin{array}{rcl}{L}_1\circ L_2& =& \{0a,0b,0helo,1a,1b,1helo\}\\ L_2\circ L_1& =& \{a0,a1,b0,b1,helo0,helo1\}\\ L_1\circ L_1& =& \{00,01,10,11\}\end{array}$$

Setakat ini kita memerihalkan bahasa dengan bahasa biasa, iaitu kita menerangkan dengan kata-kata rupa bentuk sesuatu bahasa. Cara ini sangat tidak praktikal, jadi diperkenalkan cara yang lebih formal untuk mentakrifkan bahasa. Cara pertama ialah tatabahasa.