Kekerasan menemukan kata panjang paling banyak

Pernyataan masalah :

Biarkan menjadi otomat pushdown (berpotensi tidak deterministik) dan biarkan menjadi alfabet inputnya. Apakah ada kata st yang diterima oleh ? $M$ $\cal A$ $w \in \cal A^*$ $|w| \leq k$ $M$

Apakah ini masalah NP-complete? Apakah sudah dipelajari? Apakah ada algoritma yang memungkinkan untuk menemukan kata seperti itu?

cc.complexity-theory np-hardness fl.formal-languages automata-theory Lamin
sumber

Tidakkah seharusnya algoritma Djikstra melakukan triknya? (Saya kemungkinan besar salah paham akan sesuatu di sini!)

alpoge

"panjangnya paling banyak

k

$k$ "?

alpoge

Sama-sama, Kaveh. Ya, saya lupa "paling banyak", saya edit lagi.

Lamine

Jawabannya mudah - apakah ini pertanyaan pekerjaan rumah?

Sariel Har-Peled

Apakah kita memiliki akses ke deskripsi automaton atau kita hanya memilikinya sebagai kotak hitam?

Raphael

Jawaban:

Menghitung persimpangan bahasa CFG Anda dengan bahasa biasa (jumlah ini untuk mengalikan jumlah negara dengan dan menambahkan "buntu" negara). Sekarang periksa apakah hasilnya kosong: dikonversi menjadi tata bahasa (saya pikir hasilnya akan memiliki ukuran polinomial) dan "mundur" dari produksi epsilon. $\sum_{i=0}^k A^k$ $k$

Sunting: Kaveh menyebutkan bahwa ini polinomial dalam , jadi jika diberikan sebagai input, algoritmanya eksponensial dalam . Namun, Kaveh menemukan cara untuk memperbaikinya. Konversikan robot asli menjadi CFG, dan ganti semua terminal dengan terminal tetap. Sekarang gunakan algoritma berulang untuk menemukan ukuran minimal kata yang dihasilkan oleh masing-masing non-terminal, sebagai berikut. $k$ $k$ $|k|$

$\infty$ $A \rightarrow a^t \prod B_i$ $f(A) = \min(f(A),t+\sum f(B_i))$ $O(n)$ $n$

Yuval Filmus
sumber

Saya juga berpikir bahwa transformasi PDA CFG adalah polinomial. Terima kasih! Jadi masalahnya adalah di .

\to

$\rightarrow$

P

$P$

Lamine

Oke, karena ada cara untuk menghitung langsung panjang terendah,bukan input. Tapi saya tidak mengerti mengapa mengganti semua terminal dengan yang diperbaiki. Algoritme harus beroperasi dengan benar dengan terminal asli.

| k |

$|k|$

Lamine

Anda benar, sebenarnya tidak masalah.

Yuval Filmus

Ubah semua karakter alfabet menjadi satu karakter spesifik. Sekarang, Anda memiliki PDA yang didefinisikan lebih dari satu karakter. Bahasanya adalah tata bahasa bebas konteks. Namun, tata bahasa bebas konteks atas satu karakter adalah biasa. Jadi, konversikan CFG ke dalam bahasa biasa, lalu periksa apakah mengandung panjang kata k.

Sekarang, semua konversi ini cenderung membutuhkan waktu yang eksponensial, tetapi bagi saya sepertinya masalahnya adalah NP selesai. Terutama jika Anda mengizinkan waktu polinomial dalam . $k$

Saya mungkin salah, dan saya minta maaf atas jawaban lalai awal saya ...

BTW, fakta bahwa CFG atas satu huruf adalah teratur mengikuti dari teorema Parikh. Meski bukti langsung tidak terlalu sulit. Lihat tautan untuk perincian lebih lanjut tentang teorema Parikh - ini adalah hasil yang indah ... http://www8.cs.umu.se/kurser/TDBC92/VT06/final/3.pdf

Sariel Har-Peled
sumber

Tidak, saya bukan pelajar. Masalah yang saya sebutkan pada awalnya adalah masalah jaringan yang dimodelkan sebagai otomat. Saya hanya akan tahu apakah perlu mencari solusi polinomial atau tidak.

Lamine

Tidakkah jawaban ini menjadi komentar?

Oleksandr Bondarenko

Ya seharusnya. Sariel, bisakah Anda memindahkan ini ke komentar atau memberikan jawaban?

Suresh Venkat

@ Suresh: Anda mungkin mengetahui hal ini, tetapi sekarang moderator dapat mengubah jawaban menjadi komentar .

Tsuyoshi Ito

Saya memindahkan jawaban asli ke komentar. Ini jawaban baru.

Suresh Venkat

~~Metode yang mungkin kurang optimal: Jalankan algoritma Djikstra. Kemudian, untuk setiap keadaan akhir, bandingkan jarak dengan . Jika ada yang , terima. Menolak. $k$ $\leq k$~~

EDIT: Di atas hanya berfungsi untuk NFA! Maaf soal itu.

alpoge
sumber

(tapi pasti poly-time!)

alpoge

Saya tidak yakin bahwa algoritma Dijkstra dapat menyelesaikan masalah. Itu dapat menemukan jalur terpendek antara keadaan awal dan akhir. Tentu saja, sebuah kata yang dapat diterima melalui jalur ini dapat dihasilkan. Tetapi jalur ini bersifat elementer, dan kata-kata dapat diterima melalui jalur nonelementer; jika tidak, masalah menentukan apakah tata bahasa bebas konteks dapat menghasilkan kata apa pun akan dianggap layak, tetapi tidak.

Lamine

Pengujian kekosongan untuk CFL adalah decidable, bukan?

alpoge

(Maafkan saya lagi jika saya salah paham!)

alpoge

Nah, seseorang dapat menggunakan algoritma 'penandaan' untuk melakukan ini (diberi CFG) - menandai terminal, kemudian menandai hal-hal yang berasal dari terminal, kemudian menandai hal-hal yang berasal dari hal-hal yang ditandai, dll. Hingga proses berakhir, dan kemudian memeriksa jika variabel awal ditandai. Selain itu, abaikan jawaban saya - itulah yang harus Anda lakukan untuk NFA (tentu bukan untuk PDA!).

alpoge