Bahasa formal

Bahasa formal merupakan semacam perluasan dari konsep bahasa yang sudah kita kenal dalam kehidupan sehari-hari.

Konsep dasar

Sebagai permulaan, bahasa formal dapat kita bayangkan seperti bahasa biasa, misalnya bahasa Indonesia. Terdiri atas apa bahasa seperti itu? Bahasa terdiri atas kata, yang kemudian kita rangkai menjadi kalimat. Kalimat tidak akan kita bahas, yang kita perhatikan hanya kata. Lalu, kata terdiri atas apa? Atas huruf-huruf alfabet. Karena itu, kita mulai dari alfabet.

Alfabet adalah sembarang himpunan yang tidak kosong. Anggota alfabet disebut simbol. Untuk bahasa Indonesia, alfabetnya adalah alfabet Latin biasa yang terdiri atas huruf kecil dan huruf kapital. Jika yang ingin kita gambarkan bukan bahasa Indonesia, melainkan misalnya bilangan, alfabetnya berisi kesepuluh angka. Alfabet sering dilambangkan dengan simbol Σ.

String (disebut juga untai atau kata) adalah barisan berhingga simbol dari suatu alfabet Σ. Misalnya, untuk alfabet Σ= {a,b,c,d,e,…, z}, contoh string adalah barisan “halo” atau “kucing”, tetapi bukan “e-mail” (tidak ada tanda hubung “-”), “Budi” (tidak ada huruf “B”) atau “selamat pagi” (tidak ada spasi). Panjang string adalah banyaknya simbol yang menyusun string tersebut.

Konkatenasi string: jika ada dua string a = a₁a₂… a_n dan b = b₁b₂… b_m, konkatenasi (penyambungan) keduanya menghasilkan string ab = a₁a₂… a_nb₁b₂… b_m. Contoh: konkatenasi string “halo” dan “kucing” menghasilkan string “halokucing”. Konkatenasi ditulis dengan lingkaran kecil, yaitu a ∘ b, atau tidak ditandai sama sekali dan kedua string cukup ditulis berurutan tanpa simbol khusus.

String kosong dilambangkan dengan ε, yaitu string yang panjangnya nol. Jika string a = a₁… a_n kita sambung dengan string kosong ε, kita memperoleh kembali string a. Jadi, berlaku a ∘ ε = a.

Penutup alfabet Σ adalah himpunan semua string yang dapat dibentuk dari alfabet Σ, termasuk string kosong. Penutup dilambangkan dengan Σ^∗. Untuk alfabet biner Σ= {0, 1} berlaku

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

Kadang-kadang digunakan juga penutup positif alfabet, yaitu semua string yang dapat disusun dari alfabet, kecuali string kosong. Penutup positif dilambangkan dengan Σ⁺ dan berlaku Σ⁺ = Σ^∗ ∖ {ε}.

Contoh alfabet

• Kita kembali ke contoh bahasa Indonesia. Setiap kata bahasa Indonesia dapat ditemukan dalam penutup alfabet yang memuat huruf kecil dan huruf kapital (ditambah mungkin tanda hubung “-”). Jika ke alfabet tersebut kita tambahkan spasi dan tanda baca (koma, titik, tanda seru, tanda tanya, …), penutupnya memuat semua kalimat yang dapat dibentuk dalam bahasa Indonesia. Tentu saja penutup ini juga memuat kalimat seperti “sadflsf kasdf kagrjewiqxzker kf fkjbsjbgvbadfgsa!!!:??: ::!?:?:sdf”, yang sama sekali tidak bermakna.

• Jika alfabet kita memuat semua angka Σ= {0, 1, …, 9}, penutupnya memuat semua bilangan asli, dan masih ada yang lain. Di dalamnya juga ada bilangan yang diawali nol, misalnya 00054, bilangan nol itu sendiri, dan juga string kosong, yang jelas bukan bilangan.

• Alfabet tidak boleh kosong, sehingga alfabet terkecil memiliki setidaknya satu simbol. Misalnya, untuk alfabet Σ= {!} kita memperoleh penutup Σ^∗ = {ε, !, !!, !!!, !!!!, …}, yaitu himpunan string yang untuk setiap n ∈ ℕ₀ memuat string yang terdiri atas n tanda seru, dan tidak memuat string lain.

• Misalkan Σ= {qw,c}. Alfabet ini sangat aneh karena memuat string qw. Penulisan seperti ini biasanya tidak digunakan karena membingungkan, tetapi kita dapat membayangkan bahwa huruf “q” dan “w” direkatkan menjadi satu karakter. Dengan begitu, string “qw” dapat kita pandang sebagai simbol “qw”. Jika dari simbol ini kita bentuk string “qwcqw”, panjang string tersebut adalah tiga, karena tersusun atas simbol “qw”, “c”, dan “qw”. Alfabet seperti ini jarang dijumpai, tetapi ada situasi yang memang memerlukan simbol yang tersusun atas beberapa simbol.

Bahasa formal

Bahasa (formal) atas alfabet Σ adalah sembarang himpunan bagian dari Σ^∗. Jadi, untuk bahasa L atas alfabet Σ berlaku L ⊆ Σ^∗. Contoh bahasa:

• Pada bagian sebelumnya, kita sudah mendefinisikan alfabet angka Σ= {0, 1, …, 9}. Penutupnya adalah semua string yang hanya tersusun atas angka. Jika kita tambahkan aturan bahwa string tidak boleh diawali nol dan tidak boleh kosong, kita memperoleh himpunan bilangan asli ℕ. Berlaku ℕ ⊆ Σ^∗, sehingga ℕ adalah bahasa atas alfabet Σ.

• Ke himpunan angka tadi kita masih dapat menambahkan tanda minus “-”, sehingga Σ= {0, 1, …, 9, −}. Penutupnya adalah semua string yang tersusun atas angka atau tanda minus. Artinya, penutup ini juga memuat string seperti “12-84-”, “1-5-8”, atau “-”. Bahasa bilangan bulat ℤ kita bentuk dengan menambahkan tiga aturan:

  • Tanda minus tidak muncul sama sekali dalam string atau hanya muncul di awal string.
  • Angka pertama dalam string tidak boleh nol, kecuali pada string “0”.
  • Setiap string harus memuat setidaknya satu angka.

  Himpunan ini menggambarkan himpunan bilangan bulat dan merupakan himpunan bagian dari Σ^∗ — jadi, himpunan ini adalah bahasa atas alfabet Σ.

• Misalkan Σ= {0, 1}. Penutupnya adalah semua string yang tersusun atas angka nol dan satu. Bahasa L atas alfabet ini dapat kita definisikan, misalnya, sebagai himpunan semua string yang memuat tepat tiga angka satu. Kita juga bisa lebih kreatif dan menyatakan bahwa bahasa L adalah himpunan semua string yang merupakan file berformat docx yang valid (yang dihasilkan oleh Word).

• Kita tetap menggunakan alfabet biner Σ= {0, 1}. Setiap rangkaian karakter (karakter biasa yang ada pada papan ketikmu) dapat diubah ke bentuk biner, yaitu menjadi angka nol dan satu, lalu dikembalikan lagi, misalnya dengan tabel ASCII (lebih tepatnya, tabel ASCII mengubah karakter menjadi bilangan, dan bilangan dalam sistem desimal dapat dikonversi menjadi bilangan dalam sistem biner). Dengan demikian, kita dapat mendefinisikan bahasa semua string yang merupakan alamat email yang valid, dan bahasa tersebut tetap merupakan bahasa atas alfabet biner.

Konkatenasi bahasa: bahasa juga dapat disambung. Definisinya mirip dengan hasil kali Kartesius himpunan. Misalkan ada dua bahasa L₁ dan L₂. Konkatenasi keduanya, L₁ ∘ L₂, menghasilkan bahasa baru yang didefinisikan sebagai berikut:

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

Artinya, kita ambil semua string dari bahasa L₁ dan menyambungnya dengan semua string dari bahasa L₂. Contoh: Misalkan

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

Hasilnya:

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

Sejauh ini, untuk menggambarkan bahasa kita menggunakan bahasa biasa, yaitu kita menjelaskan dengan kata-kata seperti apa bentuk bahasa tersebut. Cara ini sangat tidak praktis, sehingga diperkenalkan cara yang lebih formal untuk mendefinisikan bahasa. Cara pertama adalah tata bahasa (grammar).