Mengapa bahasa biasa disebut 'biasa'?

Saya baru saja menyelesaikan bab pertama dari Pengantar Teori Komputasi oleh Michael Sipser yang menjelaskan dasar-dasar automata terbatas.

Dia mendefinisikan bahasa reguler sebagai apa pun yang dapat dijelaskan oleh automata terbatas. Tetapi saya tidak dapat menemukan di mana dia menjelaskan mengapa bahasa biasa disebut "biasa?" Apa asal usul istilah "reguler" dalam konteks ini?

CATATAN: Saya seorang pemula jadi tolong coba jelaskan dengan istilah sederhana!

Seperti yang dikatakan Kaveh dalam sebuah komentar, Kleene menganugerahkan nama jalan kembali ketika ia memulai teori automata dan bahasa formal. Saya percaya istilah itu sewenang-wenang, meskipun sudah bertahun-tahun sejak saya membaca makalah aslinya.

Matematikawan memiliki kebiasaan membajak nomina dan kata sifat umum untuk objek dan properti matematika, kadang-kadang dengan alasan yang baik seperti geometri atau analogi atau metafora lain, dan kadang-kadang secara sewenang-wenang. Lihat saja "grup", "ring", "space", "sheaf", "atlas", "manifold", "field" dan seterusnya.

Faktanya, istilah "reguler" untuk bahasa-bahasa negara-terbatas, sementara masih lazim dalam teori automata, tidak banyak digunakan dalam sepupu aljabar, teori semigroup terbatas atau aljabar abstrak pada umumnya. Mengapa? Karena istilah tersebut sudah digunakan untuk semigroup yang dekat dengan grup dalam pengertian teknis tertentu, jadi Anda tidak dapat mencocokkan bahasa reguler dalam arti Kleene dengan semigroup reguler yang sesuai . Ketiga, Kleene mendefinisikan jenis acara lain yang disebut "pasti", yang telah banyak dipelajari untuk sementara waktu, tetapi ternyata tidak terlalu membuahkan hasil. Saat ini, rangkaian bahasa yang terbatas memainkan peran peristiwa tertentu sebagai dasar untuk acara reguler.

Istilah yang disukai dalam aljabar adalah "rasional" untuk kelas bahasa Kleene dan semi-grup dan monoids yang lebih umum. Penggunaan itu juga mencerminkan analogi penting antara istilah "rasional" dalam aljabar sebagai solusi persamaan linear dengan koefisien bilangan bulat dan konsep deret kekuatan rasional dalam automata dan teori bahasa formal.

Informasi tambahan. Makalah asli Kleene tahun 1951, berjudul "Representasi peristiwa dalam jaring saraf dan automata terbatas" dapat ditemukan di sini . Pada p. 46 itu menyelesaikan kesewenang-wenangan dari istilah "reguler" dengan pernyataan ini:

Kami saat ini akan menggambarkan kelas acara yang kami sebut "acara reguler". (Kami akan menerima saran untuk istilah yang lebih deskriptif.)

Rupanya, tidak ada yang datang dengan istilah yang lebih deskriptif. ;-)

Seperti yang sering terjadi dengan makalah mani yang mengarah pada pengembangan intensif seluruh bidang baru, terminologi dan konsep hampir tidak dapat dikenali dalam istilah saat ini. Pertama, makalah ini tentang model neuron, maka penggunaan "peristiwa" bukan "bahasa" atau "set". Istilah "peristiwa" bertahan hingga 60-an dan 70-an, bahkan setelah pentingnya konsep Kleene untuk automata dan bahasa formal jauh melebihi nilai apa pun untuk ilmu saraf.

$a^*b$$a^*$$a^+$yang kita gunakan hari ini. Motivasi Kleene adalah untuk menghindari string kosong (atau acara dengan durasi nol dalam ketentuannya). Itu adalah intuisi yang sangat cerdas sejak teori berikutnya telah menunjukkan betapa pentingnya pilihan untuk memasukkan atau mengecualikan string kosong dari definisi dalam banyak konteks. Ketiga, Kleene mendefinisikan konsep yang disebut "peristiwa pasti" dan mengembangkan acara reguler dari mereka, tetapi saat ini kami menggunakan set yang terbatas untuk tujuan tersebut. Peristiwa pasti dipelajari untuk sementara waktu, tetapi ternyata jauh lebih penting daripada peristiwa / set / bahasa biasa.

Bagaimanapun, pembacaan lengkap dari makalah ini mungkin tidak bernilai waktu siapa pun hari ini, kecuali untuk tujuan sejarah. Saya hanya membaca sekilas untuk definisi dan ide penting, dan itu menyenangkan.

Saya selalu mengerti istilah "reguler" yang berarti bahwa itu didasarkan pada pola yang berulang. Setelah Anda menghitung semua string dengan panjang tertentu, Anda telah melihat semuanya. Tidak akan ada yang baru sesudahnya.

(Tentu saja ini hanya intuisi yang kabur.)