Algoritma untuk menguji apakah suatu bahasa biasa

Apakah ada algoritma / prosedur sistematis untuk menguji apakah suatu bahasa biasa?

Dengan kata lain, diberikan bahasa yang ditentukan dalam bentuk aljabar (pikirkan sesuatu seperti ), uji apakah bahasa itu teratur atau tidak. Bayangkan kita sedang menulis layanan web untuk membantu siswa dengan semua pekerjaan rumah mereka; pengguna menentukan bahasa, dan layanan web merespons dengan "reguler", "tidak teratur", atau "Saya tidak tahu". (Kami ingin layanan web menjawab "Saya tidak tahu" sesering mungkin.) Apakah ada pendekatan yang baik untuk mengotomatisasi ini? Apakah ini bisa ditelusuri? Apakah ini dapat diputuskan (yaitu, apakah mungkin untuk menjamin bahwa kita tidak perlu menjawab "Saya tidak tahu")? Apakah ada algoritma yang cukup efisien untuk menyelesaikan masalah ini, dan dapat memberikan jawaban selain "tidak tahu" $L=\{a^n b^n : n \in \mathbb{N}\}$

Metode klasik untuk membuktikan bahwa suatu bahasa tidak teratur adalah lemma pemompaan. Namun, sepertinya membutuhkan wawasan manual di beberapa titik (misalnya, untuk memilih kata yang akan dipompa), jadi saya tidak jelas apakah ini dapat diubah menjadi sesuatu yang algoritmik.

Metode klasik untuk membuktikan bahwa suatu bahasa biasa adalah dengan menggunakan teorema Myhill – Nerode untuk mendapatkan otomat kondisi-terbatas. Ini terlihat seperti pendekatan yang menjanjikan, tetapi membutuhkan kemampuan untuk melakukan operasi dasar pada bahasa dalam bentuk aljabar. Tidak jelas bagi saya apakah ada cara sistematis untuk secara simbolis melakukan semua operasi yang mungkin diperlukan, pada bahasa dalam bentuk aljabar.

Untuk membuat pertanyaan ini diajukan dengan baik, kita perlu memutuskan bagaimana pengguna akan menentukan bahasa. Saya terbuka untuk saran, tetapi saya memikirkan sesuatu seperti ini:

L = {E : S}

$L = \{E : S\}$

di mana adalah ekspresi kata dan adalah sistem ketidaksetaraan linear atas variabel panjang, dengan definisi berikut: $E$ $S$

Setiap adalah ekspresi kata. (Ini mewakili variabel yang dapat mengambil kata apa pun di .) $x,y,z,\dots$ $\Sigma^*$
Setiap adalah ekspresi kata. (Di sini menunjukkan kebalikan dari string .) $x^r,y^r,z^r,\dots$ $x^r$ $x$
Setiap adalah ekspresi kata. (Secara implisit, , jadi mewakili simbol tunggal dalam alfabet yang mendasarinya.) $a,b,c,\dots$ $\Sigma=\{a,b,c,\dots\}$ $a,b,c,\dots$
Masing-masing adalah kata-ekspresi, jika adalah panjang-variabel. $a^\eta,b^\eta,c^\eta,\dots$ $\eta$
Rangkaian ekspresi kata adalah ekspresi kata.
Setiap adalah variabel panjang. (Ini mewakili variabel yang dapat mengambil nomor alami apa pun.) $m,n,p,q,\dots$
Masing-masing adalah variabel panjang. (Ini mewakili panjang kata yang sesuai.) $|x|,|y|,|z|,\dots$

Ini tampaknya cukup luas untuk menangani banyak kasus yang kita lihat dalam latihan buku teks. Tentu saja, Anda dapat mengganti metode tekstual lainnya dalam menentukan bahasa dalam bentuk aljabar, jika Anda memiliki saran yang lebih baik.

Saya belum punya waktu untuk berpikir banyak tentang pilihan ekspresi bahasa Anda. Kira-kira jenis bahasa apa yang dicakupnya? Jika Anda menambahkan batasan bahwa variabel kata hanya muncul sekali, apakah semua bahasa tersebut bebas konteks?

Gilles 'SO- stop being evil'

E

$E$

E ::= c^{η} ∣ x ∣ E E ∣ E^{r}

$E ::= c^η ∣ x ∣ EE ∣ E^r$

η ::= n ∣ | x |

$η ::= n ∣ |x|$

Anda dapat mengekspresikan sehingga ini melampaui bahasa bebas konteks. Namun, saya curiga masalahnya setidaknya sama sulitnya dengan memutuskan apakah tata bahasa bebas konteks mendefinisikan bahasa biasa.

{a^{n} b^{n} c^{n} ∣ n \in N}

$\{a^nb^nc^n \mid n\in\mathbb{N}\}$

Gilles 'SO- stop being evil'

@jmad, ya, itu masuk akal. Saya tidak terikat dengan pilihan ekspresi bahasa ini: jangan ragu untuk memilih sesuatu yang lain, jika Anda melihat sesuatu yang lebih tepat. Gilles, sudut serangan hebat! (Untuk pengunjung, ada hasil yang diketahui yang menunjukkan bahwa menguji apakah tata bahasa bebas konteks yang sewenang-wenang mendefinisikan bahasa reguler tidak dapat ditentukan.) tidak tahu ", dan kemudian minta algoritma yang menjawab" Saya tidak tahu "sesering mungkin.

Kelas ini tidak ditutup di bawah bintang Kleene, kan? Bisakah Anda mengekspresikan tanda kurung yang seimbang?

Gilles 'SANGAT berhenti menjadi jahat'

Jawaban:

Jawabannya adalah tidak. Memutuskan apakah tata bahasa bebas konteks yang diberikan menghasilkan bahasa reguler adalah masalah yang tidak dapat diputuskan.

Perbarui . Saya memberikan jawaban negatif ini untuk pertanyaan umum

Diberi bahasa yang ditentukan dalam bentuk aljabar, uji apakah bahasa itu teratur atau tidak

karena bahasa bebas konteks adalah solusi dari persamaan aljabar dalam bahasa: lihat Bab II, Teorema 1.4 dan 1.5 dalam buku J. Berstel Transduksi dan Bahasa Bebas Konteks .

Namun, pertanyaan yang sama dapat ditentukan untuk bahasa bebas konteks deterministik, hasil nontrivial karena Stearns [1] dan ditingkatkan oleh Valiant [2]:
[1] RE Stearns, Tes Keteraturan untuk Mesin Pushdown, Informasi dan Kontrol 11 323- 340 (1967). DOI: 10.1016 / S0019-9958 (67) 90591-8.
[2] LG Valiant. Keteraturan dan masalah terkait untuk deterministic pushdown automata J. ACM 22 (1975), hlm. 1-10.

Ada hasil positif lain, lebih dekat dengan spesifikasi yang diberikan di bagian kedua pertanyaan. Ingat bahwa subset semilinear dari adalah himpunan yang dapat didefinisikan dalam aritmatika Presburger. Ada juga himpunan bagian rasional dari . Secara khusus, himpunan bagian dari didefinisikan oleh persamaan linear adalah rasional. Sekarang, dengan subset rasional dari , dapat diputuskan apakah bahasa teratur. Memang, diketahui [Ginsburg-Spanier] bahwa adalah teratur jika dan hanya jika adalah subset yang dikenali dari $\mathbb{N}^k$ $\mathbb{N}^k$ $\mathbb{N}^k$ $R$ $\mathbb{N}^k$

L (R) = {u_{1}^{n_{1}} \dots u_{k}^{n_{k}} ∣ (n_{1}, . . ., n_{k}) \in R}

$L(R) = \{ u_1^{n_1} \dotsm u_k^{n_k} \mid (n_1, ...,n_k) \in R \}$

L (R)

$L(R)$

R

$R$

N^{k}

$\mathbb{N}^k$ dan dapat dinyatakan [Ginsburg-Spanier] apakah subset rasional yang diberikan dari dapat dikenali.

N^{k}

$\mathbb{N}^k$

S. Ginsburg dan EH Spanier., Semigroup, rumus Presburger, dan bahasa , Pacific J. Math. 16 (1966), 285-296.

S. Ginsburg dan EH Spanier. Set reguler terbatas , Proc. dari Matematika Amerika. Soc. 17 , 1043-1049 (1966).

Ini tidak menyelesaikan bagian kedua dari pertanyaan, yang mungkin tidak dapat dipastikan karena variabel kata, tetapi memberikan fragmen yang masuk akal untuk memulai.

J.-E. Pin
sumber

(a) Pedantic nit: Tidak jelas bagi saya apakah sintaks aljabar di atas cukup umum untuk mengekspresikan semua tata bahasa bebas konteks (seperti yang saya dan Gilles katakan dalam komentar), jadi tidak sepenuhnya jelas apakah hasil tertentu berlaku di sini . (B) Lebih penting: silakan mempertimbangkan pernyataan masalah yang sesuai tweak sehingga layanan web diizinkan untuk menjawab "Saya tidak tahu", dan kami ingin menemukan algoritma yang menjawab "Saya tidak tahu" jarang mungkin. Saya sebelumnya menyarankan ini di komentar; Saya akan mengedit pertanyaan untuk membuatnya lebih jelas dalam pertanyaan itu sendiri.

Saya menduga Anda dapat mengadaptasi buktinya, tetapi hasilnya tidak mengikuti. Saya pikir ada bahasa bebas konteks yang tidak bisa diungkapkan dalam formalisme ini: misalnya, bagaimana Anda mengekspresikan tanda kurung yang seimbang? Kelas bahasa tidak ditutup di bawah bintang Kleene, kan?

Gilles 'SO- stop being evil'

@Gilles, ya, aku memikirkannya. Tidak segera jelas bagi saya bagaimana mengadaptasi bukti. Bukti standar bahwa tidak dapat dipastikan apakah tata bahasa bebas konteksnya teratur adalah melalui teorema Greibach. Namun bagi saya sepertinya kelas bahasa ini tidak memenuhi premis teorema Greibach (sepertinya tidak akan ditutup di bawah rangkaian dengan set reguler dan ditutup di bawah gabungan). Mungkin ada beberapa pendekatan bukti lain yang saya tidak kenal. Saya setuju, tidak jelas bagaimana mengekspresikan bahasa tanda kurung yang seimbang dalam bentuk aljabar ini.

Baru saja menambahkan referensi.

J.-E.

Posting Anda tidak menjawab pertanyaan, karena membahas kelas bahasa yang berbeda. Bentuk-bentuk aljabar yang diizinkan di sini (dengan satu kata ekspresi) adalah (sejauh yang bisa kita katakan) tidak seumum bentuk-bentuk aljabar yang diperlukan untuk mengekspresikan bahasa bebas konteks yang sewenang-wenang. Bisa jadi kasus bahwa untuk persimpangan keduanya, masalahnya dapat diputuskan.

Gilles 'SANGAT berhenti menjadi jahat'