Dapatkah ambiguitas konstan mengurangi kompleksitas keadaan bahasa reguler?

Kami mengatakan bahwa NFA adalah Konstanta Ambigu jika ada sehingga setiap kata diterima oleh atau (persis) jalur . $M$ $k\in \mathbb{N}$ $w\in \Sigma^*$ $0$ $k$

Jika automaton secara konstan ambigu untuk , maka disebut Unambiguous FA (UFA). $M$ $k=1$ $M$

Biarkan menjadi bahasa biasa. $L$

Bisakah beberapa automaton yang selalu ambigu untuk lebih kecil dari UFA terkecil yang menerima ? Berapa jauh lebih kecil? $M_c$ $L$ $L$

Dapatkah otomat yang ambigu secara eksponensial lebih kecil daripada CFA terkecil untuk bahasa yang sama?

Hal ini diketahui bahwa ada finitely robot ambigu (terdapat , sehingga setiap kata diterima oleh hingga jalur) yang secara eksponensial lebih kecil dari yang terkecil UFA untuk bahasa yang sama, tapi saya belum melihat sesuatu tentang ambiguitas konstan. $k$ $k$

Juga, ini pertanyaan terkait yang saya posting di sini beberapa bulan yang lalu.

EDIT:

Jawaban Domotorp menunjukkan bahwa dapat direduksi secara polin ke , tetapi tidak menjawab pertanyaan apakah kita bisa mendapatkan pengurangan ruang polinomial oleh . $CFA$ $UFA$ $CFA$

Jadi pertanyaan baru menjadi: Seberapa jauh lebih kecil (linear / kuadratik / dll.) suatu dibandingkan dengan minimal ? untuk bahasa yang sama? $CFA$ $UFA$

complexity-classes fl.formal-languages automata-theory regular-language BPR
sumber

Apakah transisi

diizinkan?

ϵ

$\epsilon$

Denis

Mungkin ini bisa membantu: dalam Kupke, Pada Memisahkan Konstan dari Ambiguitas Polinomial dari Finite Automata disajikan hierarki berikut:

Saya tidak memeriksa makalah terkait karena berada di belakang paywall.

dfa ≺_{2^{n}} unfa ≺_{2^{n}} cafa ≺_{2^{n}} ??? ≺_{2^{n}} pafa ≺_{2^{n}} n f a

$\text{dfa} \prec_{2^n} \text{unfa} \prec_{2^n} \text{cafa} \prec_{2^n} \text{???} \prec_{2^n} \text{pafa} \prec_{2^n} {nfa}$

Marzio De Biasi

Terima kasih @MarzioDeBiasi, tapi sayangnya ini tidak membantu (saya juga berharap ketika saya melihat presentasi). Mereka menggunakan notasi berbeda dari yang saya gunakan (dan saya pernah melihat di makalah yang berbeda). "Ambiguitas Konstan" mereka adalah apa yang saya sebut ambiguitas terbatas, sehingga hubungan antara Cafa dan UFA mereka sudah diketahui oleh saya. Karena aplikasi saya menghitung solusi untuk masalah NPC, bahasa saya selalu terbatas, dan dengan demikian, setiap kata diterima oleh

jalur, yang mereka sebut "konstan".

O (1)

$O(1)$

Saya bertanya-tanya apakah definisi saya membantu mengurangi kompleksitas keadaan, karena saya memiliki CFA yang secara eksponensial lebih kecil daripada UFA terkecil yang saya tahu untuk dibangun, dan saya bertanya-tanya apakah mungkin bahwa tidak ada UFA kecil untuk bahasa tersebut.

@Denis, ya, tapi apakah itu akan membantu Anda mengurangi kompleksitas negara? Saya berasumsi Anda hanya bisa mengurangi jumlah tepi dengan gerakan seperti itu.

Jawaban:

Saya mengklaim bahwa jika untuk beberapa bahasa ada CFA dengan dengan negara dan atau menerima jalur untuk setiap kata, maka ada UFA dengan negara. Ide dasarnya adalah bahwa negara bagian UFA adalah (dipesan) c-tupel dari negara bagian CFA dan menerima jika dan hanya jika semua negara c menerima. Tentu saja kita juga harus memastikan bahwa ini memang perhitungan yang berbeda dan bahwa kita tidak menghitung semua permutasi, jadi untuk ini kita perlu beberapa tambahan bit penyimpanan. $s$ $0$ $c$ $C_ss^c$ $c!$ $C_s$

Deskripsi yang sedikit lebih rinci tentang ide dasar: Jika adalah keadaan UFA, maka ia memiliki transisi dari itu (membaca beberapa huruf ) ke keadaan jika dan hanya jika CFA memiliki transisi (membaca huruf ) dari ke untuk setiap . Keadaan $(s_1,\ldots,s_c)$ $a$ $(s_1',\ldots,s_c')$ $a$ $s_i$ $s_i'$ $i$ $(s_1,\ldots,s_c)$ menerima jika dan hanya jika menerima untuk setiap . Tentu saja keadaan awal UFA adalah mana adalah keadaan awal CFA. $s_i$ $i$ $(s_0,\ldots,s_0)$ $s_0$

Masalah dengan di atas adalah bahwa simulasi menjalankan CFA mungkin sama. Jadi kita menambahkan beberapa informasi tambahan, dikodekan, katakanlah, dalam grafik pada simpul yang memiliki keunggulan antara simpul dan simpul jika selama menjalankan sejauh setidaknya sekali kita punya . $c$ $c$ $i$ $j$ $c_i\ne c_j$

Sekarang kami masih memiliki masalah, bahwa kami telah menghitung semuanya kali karena kemungkinan permutasi. Kita dapat memperbaiki ini dengan mensyaratkan bahwa jika negara ke- dan ke- tetap sama hingga sekarang dan pada langkah berikutnya mereka akan berbeda, maka pada langkah berikutnya keadaan ke- harus memiliki indeks yang lebih besar. $c!$ $i$ $j$ $i$

domotorp
sumber

Terima kasih atas jawaban Anda di @domotorp. Sayangnya, saya tidak bisa mengatakan saya memahaminya. Bisakah Anda memberikan rincian lebih lanjut (mis. Bagaimana bukti keutamaan dikodekan?). Terima kasih!

Bagaimanapun saya menyadari bahwa ada juga UFA untuk bahasa itu, jadi lupakan saja. Bagaimana dengan sisa bagian dari jawaban saya?

domotorp

Saya tidak yakin saya mengikuti. Jika

adalah CFA dengan

, maka itu tidak berarti hanya ada

path untuk setiap kata

, hanya saja

dari mereka yang akan berakhir dalam keadaan menerima. Akan seperti apa keadaan UFA? Bisakah Anda mencoba memformalkannya?

M

$M$

k = c

$k=c$

c

$c$

w

$w$

c

$c$

Ini dia, saya harap sekarang sudah jelas.

domotorp