Bisakah ekspresi reguler menjadi tak terbatas?

Saya tahu bahwa bahasa yang dapat didefinisikan menggunakan ekspresi reguler dan yang dikenali oleh DFA / NFA (finite automata) adalah setara. Juga tidak ada DFA untuk bahasa $\{0^n1^n|n \ge 0\}$ . Tetapi masih dapat ditulis menggunakan ekspresi reguler (dalam hal ini bahasa non-reguler dapat) sebagai $\{ \epsilon \} \cup \{01\} \cup \{0011\}......$ . Tetapi kita tahu bahwa setiap bahasa yang memiliki ekspresi reguler memiliki DFA yang mengenalinya (bertentangan dengan pernyataan saya sebelumnya). Saya tahu ini adalah hal yang sepele, tetapi apakah definisi dari ekspresi reguler mencakup kondisi bahwa itu harus terbatas?

formal-languages regular-languages regular-expressions sashas
sumber

⊊

$\subsetneq$

Hanya catatan tambahan: jika kita menjatuhkan persyaratan DFA / NFA menjadi terbatas, kita dapat membuat otomat untuk menerima .

{0^{n} 1^{n} ∣ n \geq 0}

$\{0^n1^n\mid n\geq0\}$

Sebagai titik terminologi, kata 'automata' adalah jamak dari 'otomat'. Tidak ada kata 'automatas' - Anda tidak dapat membuatnya lebih jamak dari yang sudah ada. (Automata benar sebagai posesif tetapi bukan sebagai jamak)

chasly dari Inggris

Jawaban:

Jika ekspresi reguler dibiarkan tanpa batas, maka bahasa apa pun akan teratur.

Mengingat bahasa , kita selalu dapat menentukan ekspresi reguler , yang persis mendefinisikan . (Contoh: ekspresi reguler mendefinisikan $L=\{w_1, w_2, \ldots\}$ $R = w_1 + w_2 + \cdots$ $L$
$R_1 = \epsilon+0+1+00+01+10+11+\cdots$ .) $L_1=\{0,1\}^*$

Kita tahu bahwa beberapa bahasa tidak teratur, jadi ini menunjukkan bahwa ekspresi reguler yang tak terbatas menggambarkan kelas bahasa yang lebih besar daripada ekspresi reguler yang terbatas.

Ran G.
sumber

Saya suka jawaban ini, karena tidak hanya mengatakan bahwa ekspresi reguler yang tak terbatas berbeda, tetapi konsep secara keseluruhan tidak bermakna.

jmite

Pernyataan yang lebih ringkas tentang poin yang saya makamkan di paragraf kedua saya, dan karenanya lebih jelas.

Davislor

Tapi itu diakhiri dengan tautologi murni. Jadi, mengapa kita tidak menganggap semua bahasa biasa, jika mereka memiliki formulir ini? Hal-hal yang kami lakukan dengan regex tidak lagi berfungsi. Kami tidak dapat membangun mesin keadaan dengan algoritma induktif karena tidak pernah selesai dan memiliki keadaan tanpa batas. Kami tidak dapat membandingkan dengan semua yang ada dalam daftar dan menolak jika tidak ada yang cocok. Lagipula kita tidak bisa secara fisik mewakili daftar. (Daftar yang dapat kita hasilkan dengan komputer adalah bahasa yang dapat didekati.) Kita dapat membuktikan hal-hal menggunakan fakta bahwa setiap bahasa memiliki formulir ini, tetapi bukan jenis hal yang kita ketahui tentang regex.

Davislor

@jmite "tidak berarti" atau kasus khusus?

BAR

@BAR Tidak bermakna, karena di kelas bahasa lebih dari

dijelaskan oleh ekspresi reguler tak terbatas hanya

yaitu himpunan semua bahasa. Kami tidak mendapatkan kelas bahasa seperti yang Anda lakukan dengan RE terbatas, CFG, atau bahkan Mesin Turing.

Σ

$\Sigma$

2^{Σ}

$2^{\Sigma}$

jmite

Ya, itu harus terbatas. Bayangkan Anda memiliki pasangan yang cocok tanpa batas, dan input Anda adalah 011. Apakah Anda pernah bisa menolaknya? Apakah Anda pernah kehabisan pertandingan untuk memeriksa?

Apakah ada bahasa yang, menurut definisi itu, tidak akan teratur ? Bagaimana dengan himpunan semua pasang program dan input sehingga program yang diberikan berhenti pada input yang diberikan?

Sekarang, jika Anda memiliki program yang menyebutkan string dalam bahasa dalam urutan leksikografis—

Memperbarui

Untuk mengklarifikasi sedikit berdasarkan umpan balik dalam komentar, alasan mengapa tidak semua bahasa dari formulir ini teratur menurut definisi. Jika, misalnya, Anda mencari bukti teorema Kleene, itu tergantung pada kenyataan bahwa ekspresi reguler harus terbatas untuk membuktikan bahwa itu menghasilkan mesin keadaan terbatas.

Mengapa kita mendefinisikan bahasa "biasa" dengan cara itu? Karena setiap bahasa formal adalah bagian dari string pada alfabet, dan setiap rangkaian string dapat dinyatakan sebagai gabungan dari lajang, jadi jika kita menyebut rangkaian string sebagai bahasa "biasa", bahasa biasa hanya akan menjadi sinonim untuk bahasa . Itu bukan definisi yang sangat berguna, terutama karena kita tidak bisa benar-benar mengimplementasikannya dalam perangkat keras atau perangkat lunak. Kami tidak dapat menyimpan daftar tak terbatas sembarang tempat atau membangun mesin kondisi tak terbatas.

Seperti yang saya sebutkan, jika Anda memiliki cara untuk menghitung semua string dalam suatu bahasa secara berurutan, Anda dapat membangun penentu dari itu (menerima ketika Anda melihat string yang tepat itu, menolak ketika Anda menemukan string yang datang setelah yang Anda sedang mencari) dan sebaliknya (untuk setiap string secara berurutan, jalankan melalui penentu dan output jika dan hanya jika itu diterima). Jadi, jika kita menganggap setiap bahasa enumerable teratur , setiap bahasa yang dapat dideklarasikan akan menjadi “reguler” dan kita akan membutuhkan istilah baru untuk bahasa yang dikenali oleh mesin negara berhingga dan penyandiannya yang setara sebagai ekspresi terbatas.

Davislor
sumber

Jawaban ini salah. Fakta saja bahwa beberapa representasi bahasa tidak cocok untuk membangun penentu algoritmik dengan cara naif tidak menyiratkan bahwa representasi ini salah; mungkin ada pendekatan lain. Bahkan, setiap bahasa yang dapat didekati memiliki representasi dari bentuk yang diusulkan sasha! Singkatnya, Anda melakukan kekeliruan "Saya tidak bisa melihat bagaimana, jadi itu tidak mungkin".

Raphael

@Raphael: Silakan pertimbangkan implikasi pernyataan Anda, " setiap bahasa yang dapat dipercaya memiliki representasi dari bentuk yang Sasha usulkan!" Sebenarnya, itulah poin yang saya buat dalam jawaban saya. Pertanyaannya adalah, apakah semua bahasa dalam formulir ini didefinisikan sebagai reguler? Nah, apakah setiap bahasa yang dianggap biasa itu biasa? (Dan, seperti yang saya tunjukkan, beberapa yang tidak pasti juga?) Apakah itu akan menjadi definisi yang berguna tentang "reguler?"

Davislor

Selain itu, jauh dari kejatuhan bahwa penentu untuk daftar string yang tidak terbatas tidak dapat dilakukan, kalimat terakhir saya adalah petunjuk tentang bagaimana hal itu dapat dilakukan: jika daftar string disusun dengan baik, Anda dapat menolaknya segera saat Anda menemukan string melewatinya dalam pemesanan. Namun, mesin keadaan terbatas tidak dapat melakukan ini karena tidak dapat mewakili semua keadaan telah dibandingkan dengan setiap string dalam daftar yang tak terbatas, dan tidak ada yang bisa ekspresi reguler. Jika mereka bisa, mereka akan cukup kuat untuk mengenali semua bahasa yang dapat dipilih.

Davislor

Misalkan ungkapan reguler diizinkan menjadi tak terbatas.

Dengan demikian bahasa yang didefinisikan oleh {ϵ} ∪ {01} ∪ {0011} ... akan teratur. Untuk setiap bahasa reguler ada NFA. Salah satu cara untuk mendapatkan NFA ini adalah memiliki masing-masing NFA untuk setiap {ϵ}, {01}, {0011} ... dan menggabungkannya menggunakan transisi ϵ. Karena ada ekspresi reguler berbeda yang tak terbatas, kita akan perlu sub-NFA tak terbatas untuk digabungkan. Namun NFA hanya dapat memiliki jumlah negara terbatas (definisi NFA).

Dengan demikian tidak ada NFA yang dapat mendefinisikan bahasa yang didefinisikan oleh penyatuan ekspresi reguler yang tak terbatas, yang menyiratkan bahasa tersebut tidak teratur.

Dengan demikian tidak ada ekspresi reguler yang dapat mendefinisikan bahasa yang sama dengan bahasa yang didefinisikan oleh penyatuan ekspresi reguler yang tak terbatas.

Dengan demikian, ekspresi reguler hanya dapat memiliki ekspresi terbatas.

Anurag Peshne
sumber

"Ekspresi reguler tak terhingga" Anda lalu tentukan kelas bahasa lain, bukan lagu biasa. Bahkan, mereka mampu mendefinisikan setiap bahasa apapun, dan yang benar-benar tidak menarik (mereka tidak terbatas, sehingga sulit untuk bekerja dengan, dan mereka bisa melakukan apa saja, sehingga tidak ada studi dalam hal keterbatasan).

vonbrand