Apakah XOR automata (NXA) untuk bahasa yang terbatas mendapat manfaat dari siklus?

Xor automata (NXA) yang non-deterministik secara sintaksis adalah NFA, tetapi sebuah kata dikatakan diterima oleh NXA jika memiliki jumlah jalur penerimaan yang ganjil (daripada setidaknya satu jalur penerimaan dalam kasus NFA).

Sangat mudah untuk melihat bahwa untuk bahasa reguler berhingga , terdapat NFA minimal yang tidak mengandung siklus apa pun (jika suatu siklus dapat dicapai dari keadaan awal dan Anda mendapatkannya dari keadaan menerima) - bahasa Anda tidak terbatas).$L$

Ini belum tentu demikian untuk NXA.

Ditunjukkan oleh kompleksitas xor-state dari bahasa ,$xsc(L)$$L$

dan oleh yang kompleksitas negara XOR asiklik dari (yaitu ukuran NXA asiklik terkecil yang menerima ).L$axsc(L)$$L$$L$

Benarkah bahwa untuk setiap bahasa berhingga $L$ :

$$axsc(L)=xsc(L)\ ?$$

Saya pikir jawabannya adalah afirmatif. Mungkin ada bukti yang lebih sederhana, tetapi di sini ada sketsa bukti yang menggunakan aljabar linier.

Seperti domotorp, kita akan melihat konfigurasi otomat XOR n- status sebagai vektor dalam V = GF (2) ⁿ .

Biarkan L menjadi bahasa yang terbatas di atas alfabet Σ = {1, ..., k }, dan pertimbangkan otomat XOR untuk L dengan jumlah minimum status. Biarkan n menjadi jumlah negara. Kami berasumsi bahwa status diberi label 1,…, n , dan status 1 adalah status awal.

Pertama-tama kita mengatur notasi. Mari v ₀ = (1, 0, ..., 0) ^T ∈ V menjadi vektor dasar yang sesuai dengan keadaan awal, dan membiarkan s menjadi vektor baris yang saya masuk th adalah 1 jika dan hanya jika negara saya adalah negara menerima. Subruang R = { v : s v = 0} dari V sesuai dengan vektor konfigurasi yang ditolak.

Untuk setiap satu ∈Σ, biarkan A _yang menjadi n × n matriks lebih GF (2) yang merupakan transisi yang disebabkan oleh surat a . Misalnya, vektor konfigurasi setelah membaca input string a b adalah A _b A _a v ₀ . Untuk string σ = a ₁ ... a _t , kami menyatakan produk A _{a t} ... A _{a 1} oleh M ( σ ). Misalkan S = { A ₁, ..., A _k }.

Sebuah subruang W dari V dikatakan S - invarian ketika A W ⊆ W untuk setiap A ∈ S . Dalam konteks kami, ini berarti bahwa setelah vektor konfigurasi masuk ke W , tidak ada jalan keluar dari W dengan membaca lebih banyak huruf.

Karena otomat XOR ini memiliki jumlah minimum status, kami memiliki properti berikut.

• Satu-satunya subruang S -invari dari V yang berisi v ₀ adalah V itu sendiri. Ini karena jika W adalah subruang S -invariant yang tepat yang mengandung v ₀ , maka kita dapat menggunakan W sebagai pengganti V , yang bertentangan dengan minimalitas.
• Satu-satunya subruang S -invarian yang terkandung dalam R adalah {0}. Ini karena jika W adalah subruang S- invasif nontrivial yang terkandung dalam R , maka kita dapat menggunakan ruang vektor hasil bagi V / W di tempat V , sekali lagi bertentangan dengan minimalitas.

Karena L adalah terbatas, biarkan m integer lebih besar dari panjang string apapun dalam L .

Lemma 1 . Untuk string σ dengan panjang setidaknya m , kita memiliki M ( σ ) = 0.

Bukti. Pertama kita buktikan bahwa untuk setiap string σ dengan panjang setidaknya m , kita memiliki M ( σ ) v ₀ = 0. Misalkan W adalah subruang dari V yang direntang oleh { M ( σ ) v ₀ : σ adalah string dengan panjang setidaknya m }. Menurut definisi, W adalah S- invarian. Karena robot XOR yang bersangkutan menolak string ini σ , W terkandung dalam R . Karenanya W = {0}, yang artinyaM ( σ ) v ₀ = 0 untuk semua string seperti itu σ .

Sekarang perhatikan setiap vektor v ∈ V . Karena satu-satunya subruang S -invari dari V yang berisi v ₀ adalah V itu sendiri, v dapat ditulis sebagai kombinasi linear dari vektor-vektor dari bentuk M ( τ ) v ₀ untuk beberapa string τ . Karena M ( σ ) M ( τ ) v ₀ = M ( τ σ ) v ₀= 0 (persamaan terakhir mengikuti dari paragraf sebelumnya karena panjang τ σ setidaknya m ), menyatakan bahwa M ( σ ) v = 0. ■

Kita perlu satu fakta lagi dari aljabar linier.

Lemma 2 . Misalkan A ₁ ,…, A _k menjadi n × n matriks di atas bidang, dan tentukan M ( σ ) seperti di atas. Jika ada m ≥0 sehingga M ( σ ) = 0 untuk setiap string σ dengan panjang setidaknya m , maka matriks A ₁ ,…, A _k secara bersamaan mirip dengan matriks segitiga yang sangat rendah (yaitu, ada n × n nonsingular matriks P sehingga matriks P ^-1 A₁ P ,…, P ⁻¹ A _k P benar-benar segitiga lebih rendah).

Kasus k = 1 adalah karakterisasi terkenal dari matriks nilpotent, dan Lemma 2 dapat dibuktikan dengan cara yang sama.

Sekarang perhatikan otomat X - n-negara di mana matriks transisi yang sesuai dengan simbol a ∈Σ diberikan oleh P ⁻¹ A _a P , vektor konfigurasi awal diberikan oleh P ⁻¹ v ₀ , dan vektor karakteristik (baris) dari negara-negara menerima diberikan oleh s P . Dengan konstruksi, robot XOR ini menerima bahasa yang sama L. Karena matriks transisi adalah segitiga yang benar-benar lebih rendah, setiap tepi transisi dalam otomat XOR ini berubah dari keadaan dengan indeks yang lebih kecil ke keadaan dengan indeks yang lebih besar, dan oleh karena itu otomat XOR ini asiklik. Meskipun vektor konfigurasi awal mungkin memiliki lebih dari satu 1s, mudah untuk mengubah otomat XOR ini menjadi otomat XOR biasa dengan keadaan awal tunggal untuk bahasa yang sama tanpa meningkatkan jumlah keadaan atau merusak asiklikitas.

Saya pikir saya bisa membuktikan bahwa siklus tidak membantu alfabet unary.

Pertimbangkan matriksnya $M$ lebih $F_2$ menggambarkan dari negara mana ke negara mana kita bisa mendapatkan dalam satu langkah dan vektor $v_n$ lebih $F_2$ menggambarkan kemungkinan keadaan otomat $\mod 2$ setelah $n$ langkah-langkahnya $v_n=M^nv_0$dimana $v_0=(1,0,..,0)$menggambarkan kondisi awal. Jika kita tahu itu setelah beberapa terbatas$t$ Langkah $s\cdot v=0$ (dimana $s$adalah vektor karakteristik dari negara penerima), itu berarti bahwa kita berada dalam subruang tertentu. Dimensi dari$M^n$benar-benar turun monoton untuk sementara waktu, kemudian konstan. Ini berarti bahwa kita harus mencapai subsapce$s\cdot v_n=0$setelah paling banyak langkah, seperti banyak negara otomat miliki. Tapi kemudian ada otomat bebas siklus yang hanya menghitung panjang kata.