Mengapa bahasa biasa disebut "biasa"?

27

Mengapa bahasa reguler (dan dari ekspresi reguler itu) disebut "reguler"? Ada banyak keteraturan juga dalam bahasa bebas konteks dari jenis bahasa lainnya.

Saya menduga bahwa, pada awalnya, kata sifat "biasa" telah digunakan untuk membedakan jenis bahasa itu dari bahasa "non-reguler" atau entah bagaimana abnormal lainnya. Jika demikian, di mana jenis-jenis ini, dan apa yang tidak teratur mereka ?

regular-expressions regular-language ho.history-overview Gioele
sumber
1
tidak ada alasan yang lebih baik daripada alasan mengapa subkelompok normal disebut "normal"?
Sasho Nikolov
2
@SashoNikolov: math.stackexchange.com/questions/898977/…
Joshua Grochow

Jawaban:

39

Pemeriksaan cepat dari sumber mengungkapkan bahwa Chomsky menyebut level hierarki-nya hanya "tipe 0, tipe 1, tipe 2, tipe 3". Dia menyebutkan dalam catatan kaki bahwa tipe 3 sesuai dengan "acara reguler" dari Kleene . Kleene menulis di sana: Kami saat ini akan menggambarkan kelas peristiwa yang akan kami sebut "acara reguler." (Kami akan menerima saran untuk istilah yang lebih deskriptif.)

Dengan demikian akan muncul bahwa istilah ini adalah kecelakaan historis, dan dalam hal apapun tidak ada kaitannya dengan hubungan bahasa reguler dengan bahasa bebas konteks.

Emil Jeřábek mendukung Monica
sumber
6
p−l−1p
9
Makalah ini juga menunjukkan bahwa kita harus berterima kasih kepada Kleen jika bahasa reguler disebut "biasa" dan bukan "bisa dipikirkan sebelumnya".
gioele