✖

Ungkapan nalar

Ungkapan nalar (regular expression) ialah rentetan teks yang membolehkan kita memerihalkan suatu set rentetan. Ungkapan nalar juga boleh difahami sebagai cara mudah untuk memerihalkan automaton terhingga.

Apakah ungkapan nalar

Dalam aritmetik, kita menggunakan simbol seperti · dan + untuk membina ungkapan, contohnya (2 + 3) · 4. Apabila ungkapan ini dinilai, kita memperoleh suatu nombor. Ungkapan nalar ialah jujukan aksara dan beberapa simbol khas, contohnya a(x ∪ y), yang apabila dinilai menghasilkan bahasa (formal). Hasil ungkapan (2 + 3) · 4 ialah nombor 20, manakala hasil ungkapan nalar a(x ∪ y) ialah set dua rentetan, iaitu “ax” dan “ay”.

Bagaimanakah kita menilai ungkapan nalar a(x ∪ y) tadi? Setiap huruf sebenarnya ialah singkatan bagi set satu unsur yang mengandungi huruf itu, dan pendaraban tersembunyi ialah perangkaian rentetan. Ungkapan nalar itu boleh ditulis semula “secara lengkap” seperti berikut:

{a}∘({x}∪{y})

Seterusnya kita menilainya begini: kesatuan {x} ∪ {y} menghasilkan bahasa {x,y}. Perangkaian bahasa {a} dan {x,y} menghasilkan bahasa {ax, ay}.

Ungkapan nalar sangat kerap digunakan dalam pengaturcaraan, dan kebanyakan bahasa pengaturcaraan melaksanakan ungkapan nalar dalam satu bentuk atau yang lain. Ungkapan nalar digunakan, misalnya, untuk menyemak sama ada teks yang dimasukkan oleh pengguna memenuhi kriteria tertentu (contohnya, sama ada teks itu alamat e-mel yang sah, tarikh yang sah dan sebagainya), dan juga untuk menggantikan teks (contohnya, kita mungkin mahu menggantikan semua URL dalam teks dengan pautan yang boleh diklik).

Pelaksanaan sebenar ungkapan nalar biasanya lebih berkuasa daripada ungkapan nalar yang diterangkan di sini, dan menggunakan sintaks yang sedikit berbeza dan, yang paling penting, lebih rumit.

Takrif ungkapan nalar

Kita mentakrifkan ungkapan nalar atas suatu abjad Σ. Kita katakan bahawa ungkapan nalar ialah:

  1. a, dengan a ∈ Σ. Maksudnya, satu aksara abjad ialah ungkapan nalar.
  2. ϵ: rentetan kosong; dalam pengaturcaraan juga ditulis sebagai tanda petik kosong “”.
  3. ∅: ungkapan nalar mesti dapat memerihalkan bahasa kosong juga, jadi bahasa kosong ialah ungkapan nalar.
  4. (R1 ∪ R2), dengan R1, R2 ialah ungkapan nalar.
  5. (R1 ∘ R2), dengan R1, R2 ialah ungkapan nalar.
  6. (R∗), dengan R ialah ungkapan nalar.

Simbol ∪ dalam perkara 4 boleh digantikan dengan simbol garis tegak: |. Simbol ∘ pula tidak perlu ditulis langsung. Sebagaimana kita biasanya tidak menulis simbol pendaraban, iaitu titik tengah ·, kita juga biasanya tidak menulis simbol perangkaian ∘. Oleh itu, kedua-dua ungkapan nalar ini sama: a ∘ (b ∪ c) dan a(b|c).

Apakah maksud setiap pengendali?

  • ∪ atau | ialah kesatuan bahasa.
  • ∘ ialah perangkaian bahasa.
  • ∗ ialah tutupan bahasa.

Contoh:

  • a mewakili bahasa ringkas {a}.
  • a|b mewakili bahasa yang terdiri daripada dua rentetan {a, b}.
  • a ∘ b mewakili bahasa {ab}.
  • a(b|c)d mewakili bahasa {abd, acd}.
  • a(b∗) mewakili bahasa semua rentetan yang bermula dengan huruf “a” dan diikuti oleh sebarang bilangan huruf “b”.
  • (ab)∗ mewakili bahasa semua rentetan {ϵ, ab, abab, ababab, …}.
  • 0∗10∗ mewakili bahasa semua rentetan binari yang mengandungi tepat satu digit satu. (Perhatikan bahawa lebih tepat jika ungkapan ini ditulis sebagai (0∗)1(0∗), tetapi apabila tatatanda itu jelas tanpa kurungan, kurungan boleh ditinggalkan.)
  • Σ∗1Σ∗ mewakili bahasa semua rentetan yang mengandungi sekurang-kurangnya satu digit satu.
  • (1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)∗ mewakili bahasa semua nombor asli.

Seterusnya kita akan menunjukkan kesetaraan antara ungkapan nalar dengan automaton terhingga. Bagi setiap ungkapan nalar yang menghasilkan bahasa R, wujud automaton terhingga A yang memenuhi L(A) = R, dan begitu juga sebaliknya.

Sumber

Kandungan: Ungkapan nalar, Penukaran ungkapan nalar kepada automaton, Automaton terhingga tak berketentuan umum, Penukaran automaton kepada ungkapan nalar