Menghitung kata-kata yang diterima oleh tata bahasa biasa

Diberi bahasa reguler (NFA, DFA, grammar, atau regex), bagaimana cara menghitung jumlah kata yang menerima dalam bahasa tertentu? Keduanya "dengan tepat n huruf" dan "dengan paling banyak n huruf" menarik.

Margareta Ackerman memiliki dua makalah tentang masalah terkait penghitungan kata-kata yang diterima oleh NFA, tetapi saya tidak dapat memodifikasinya untuk menghitung secara efisien.

Sepertinya sifat terbatas dari bahasa biasa seharusnya membuat penghitungannya relatif mudah - Saya hampir mengharapkan rumus lebih dari satu algoritma. Sayangnya pencarian saya sejauh ini belum menghasilkan apa-apa, jadi saya harus menggunakan istilah yang salah.

Untuk DFA, di mana keadaan awal adalah keadaan , jumlah kata dengan panjang yang berakhir pada keadaan adalah , di mana adalah matriks transfer DFA (matriks di mana angka pada baris dan kolom adalah jumlah simbol input yang berbeda yang menyebabkan transisi dari status ke status ). Jadi, Anda dapat menghitung kata-kata yang menerima panjang persis dengan mudah, bahkan ketika cukup besar, hanya dengan menghitung kekuatan matriks dan menambahkan entri yang sesuai dengan negara penerima.k i A k [ 0 , i ] A i j i j k $0$$k$$i$$A^k[0,i]$$A$$i$$j$$i$$j$$k$$k$

Hal yang sama berfungsi untuk menerima kata-kata panjang paling banyak , dengan matriks yang sedikit berbeda. Tambahkan baris dan kolom tambahan dari matriks, dengan satu di sel yang ada di baris dan kolom, satu di baris baru dan kolom dari kondisi awal, dan nol di semua sel lainnya. Efek dari perubahan ini ke matriks adalah menambahkan satu jalur lagi ke keadaan awal pada setiap daya.$k$

Ini tidak berfungsi untuk NFA. Saya menduga hal terbaik untuk dilakukan adalah hanya mengkonversi ke DFA dan kemudian menerapkan algoritma powering matrix.

Biarkan menjadi otomatisasi terbatas (nondeterministic) dengan keadaan awal , dan .q 1 Q F ⊆ Q δ ⊆ Q × Σ × $A = (Q = \{q_1, \dots, q_n\}, \Sigma, \delta, Q_F)$$q_1$$Q_F \subseteq Q$$\delta \subseteq Q\times\Sigma\times Q$

Misalkan fungsi pembangkit untuk semua kata yang dapat diterima mulai dari , yaitu koefisien ke- dari ekspansi.q i n [ z n ] Q i = | { w ∣ | w | = n ∧ w  diterima dari  q i } $Q_i(z)$$q_i$$n$$[z^n]Q_i = |\{w \mid |w| = n \wedge w \text{ accepted from } q_i\}|$

Jelas:

$Q_i(z) = \left[ q_i \in Q_F \right] + \sum\limits_{(q_i, a, q_j) \in \delta} x \cdot Q_j(z)$

Selesaikan sistem persamaan (linier) yang dihasilkan untuk (menggunakan Mathematica atau alat serupa). Kemudian, adalah jumlah yang diinginkan. [ z n ] Q $Q_1$$[z^n]Q_1$

Ini kembali ke teknik yang diperkenalkan untuk tata bahasa oleh Chomsky dan Schützenberger (1963); dengan mudah mentransfer ke automata terbatas.

Sunting: Jika Anda ingin memperhitungkan -transisi, tinggalkan saja faktor dalam jumlah untuk transisi yang sesuai. Demikian pula, jika Anda memiliki tepi "terkompresi", yaitu sebagai ganti simbol kata pada transisi, ganti dengan .x a ∈ Σ w ∈ Σ k x x $\varepsilon$$x$$a \in \Sigma$$w \in \Sigma^k$$x$$x^k$

Saya pikir ini adalah masalah penghitungan yang sulit, lihat makalah ini: Menghitung ukuran urutan teratur panjang yang diberikan adalah # P-lengkap: S. Kannan, Z. Sweedyk, dan SR Mahaney. Menghitung dan menghasilkan string secara acak dalam bahasa reguler. Dalam ACM-SIAM Simposium tentang Algoritma Diskrit (SODA), halaman 551–557, 1995.

$\#\mathsf{NC}^1$