Mengapa tidak mudah untuk menghitung jumlah kata dalam bahasa biasa?

8

Diberi DFA, A, misalkan L (A) menunjukkan jumlah kata yang diterima A. Saya pikir mudah untuk menghitung L (A): Terjemahkan pengkodean A ke dalam ekspresi reguler. Jika bintang Kleene muncul di mana saja dalam ekspresi - bahasanya tidak terbatas. Lain: Periksa dan hitung semua kombinasi kata yang memungkinkan untuk dibuat menggunakan ekspresi (pada dasarnya jika ada operator + pada ekspresi, kalikan jumlah kata hukum dengan jumlah string yang dihubungkan oleh + ..)

Apakah ini salah? Terima kasih sebelumnya

regular-languages automata regular-expressions pengguna67573
sumber

3

ε^{*}

$\varepsilon^*$ bukan bahasa tak terbatas.

David Richerby

cstheory.stackexchange.com/q/8200/5038

DW

12

Yap, ini salah, karena ambiguitas.

Pertimbangkan bahasa berikut: $(a + aa) + a(a + \epsilon)$ .

Dengan metode Anda, kami melihat 4 kata, $a, aa, aa, a$ . Tapi kami punya duplikat! Ada beberapa cara untuk membuat kata yang sama dalam ekspresi reguler yang diberikan.

Metode yang lebih baik adalah dengan menggunakan pemrograman dinamis pada DFA minimal untuk bahasa Anda, tanpa status "mati". Jika DFA minimal adalah siklik, bahasanya tidak sempurna, jadi kita dapat mengasumsikan tidak ada siklus. Menggunakan DFA adalah kuncinya, karena determinisme berarti hanya ada satu jalur melalui DFA untuk setiap kata.

Apa yang Anda lakukan adalah membangun pengulangan untuk jumlah kata yang berakhir pada kondisi tertentu:

1 kata berakhir pada status awal: $\epsilon$
Untuk setiap negara bagian $q$ , jumlah kata yang berakhir di sana adalah jumlah dari jumlah kata yang berakhir di setiap negara bagian dengan transisi ke $q$ .

Jumlah total kata adalah jumlah dari jumlah kata yang berakhir pada setiap kondisi akhir.

Ya ampun
sumber

2

Perlu dicatat bahwa rekurensi ini selalu dapat diselesaikan dengan aljabar komputer, misalnya untuk fungsi pembangkit. Jadi ya, bahasa biasa yang sebenarnya mudah untuk menghitung.

Raphael

9

Melengkapi jawaban jmite, tidak terlalu sulit untuk menghitung jumlah kata dalam bahasa reguler, menggunakan metode "transfer matrix". Ini sama dengan pemrograman dinamis jmite, tetapi teknik ini memiliki aplikasi lebih lanjut seperti enumerasi asimptotik.

Diberi DFA, buat a $Q\times Q$ matriks $M$ (dimana $Q$ adalah himpunan negara) di mana $M(i,j)$ adalah jumlah huruf yang menyebabkan DFA pindah dari negara $j$ untuk menyatakan $i$ . Membiarkan $1_{q_0}$ dan $1_F$ menjadi indikator untuk masing-masing negara bagian dan negara penerima. Akhirnya, biarkan $n = |Q|$ .

Jumlah kata-kata panjang $m$ adalah $c_m := 1_F M^m 1_{q_0}$ . Menghitung $c_m$ untuk $0 \leq m < 2n$ . Jika $c_n + \cdots + c_{2n-1} > 0$ maka bahasa yang diterima oleh DFA tidak terbatas. Kalau tidak, jumlah kata dalam bahasa adalah $c_0 + \cdots + c_{n-1}$ .

(Ketika kekuatan komputasi $M$ , harus diperhatikan tentang besarnya entri, yang bersifat eksponensial dalam $m$ . Karena ukurannya hanya polinomial, algoritma yang dihasilkan berjalan dalam waktu polinomial.)

Yuval Filmus
sumber

2

Saya suka pendekatan ini. Saya juga menemukan bahwa menghitung nilai eigen dari

M

$M$ sebenarnya sesuai dengan akar penyebut dalam pendekatan fungsi pembangkit, dan bahwa, mungkin tidak mengejutkan, nilai-nilai eigen ini tidak berubah dari minimalisasi DFA. Namun, saya sama sekali tidak tahu bagaimana menafsirkan ini dengan benar.

Lee

1

Ini tidak begitu mengejutkan, mengingat bahwa fungsi pembangkitnya adalah

P (z) = \sum_{n = 0}^{\infty} 1_{F} M^{n} 1_{q_{0}} z^{n}

$P(z) = \sum_{n=0}^\infty 1_F M^n 1_{q_0} z^n$ , yang disederhanakan menjadi

P (z) = 1_{F} (I - z M)^{- 1} 1_{q_{0}}

$P(z) = 1_F (I-zM)^{-1} 1_{q_0}$ . Anda bisa mendapatkan hasil yang lebih eksplisit dengan mengulangi perhitungan ini menggunakan bentuk Jordan dari

M

$M$ , yang menampilkan nilai eigen.

Yuval Filmus

7

Sebenarnya, Anda masih dapat memperoleh rumus penghitungan untuk ekspresi reguler yang tidak ambigu dengan bintang-bintang Kleene di dalamnya.

Diberi definisi induktif dari ekspresi reguler sebagai:

e \in R e := x \in Σ ∣ e_{0} e_{1} ∣ e_{0} + e_{1} ∣ e^{*}

$\begin{equation*} e \in \mathrm{Re} := x \in \Sigma \mid e_0 ~ e_1 \mid e_0 + e_1 \mid e^* \end{equation*}$

Pertimbangkan terjemahan berikut $[\![\cdot]\!] : \mathrm{Re} \to \mathbb{C}(z)$ yang mengambil ekspresi reguler dan menerjemahkannya ke dalam fungsi rasional bernilai kompleks:

\begin{aligned} [[x \in Σ]] & = z \\ [[e_{0} e_{1}]] & = [[e_{0}]] \times [[e_{1}]] \\ [[e_{0} + e_{1}]] & = [[e_{0}]] + [[e_{1}]] \\ [[e^{*}]] & = \frac{1}{1 - [[e]]} \end{aligned}

$\begin{align*} [\![x \in \Sigma]\!] &= z \\ [\![e_0 ~ e_1]\!] &= [\![e_0]\!] \times [\![e_1]\!]\\ [\![e_0 + e_1]\!] &= [\![e_0]\!] + [\![e_1]\!]\\ [\![e^*]\!] &= \frac{1}{1 - [\![e]\!]} \end{align*}$

Kami dapat menunjukkan bahwa terjemahan ini mengembalikan ekspresi rasional dengan melakukan induksi struktural $e$ , dan mencatat bahwa semua operasi yang digunakan di sisi kanan menjaga rasionalitas.

Misalkan kalimat biasa $e$ yang kita masukkan tidak ambigu, maka kita akan menemukan bahwa fungsi rasional dilambangkan dengan $[\![e]\!] \in \mathbb{C}(z)$ sebenarnya adalah fungsi pembangkit untuk keluarga kata-kata yang diterima oleh bahasa yang mendasarinya $e$ , diurutkan berdasarkan panjangnya.

Misalnya, pertimbangkan bahasanya $(a^*b)^*$ , yang mendefinisikan bahasa run dari $a$ dibatasi oleh $b$ . Sekarang, ekspresi reguler ini tidak ambigu, sehingga kami dapat menjalankan trik terjemahan kami:

\begin{aligned} [[(a^{*} b)^{*}]] & = \frac{1}{1 - [[a^{*} b]]} \\ = \frac{1}{1 - ([[a^{*}]] \times [[b]])} \\ = \frac{1}{1 - (\frac{1}{1 - [[a]]} \times z)} \\ = \frac{1}{1 - \frac{z}{1 - z}} \\ = \frac{1}{2} + \frac{1}{2 - 4 z} \end{aligned}

$\begin{align*} [\![(a^*b)^*]\!] &= \frac{1}{1 - [\![a^*b]\!]} \\ &= \frac{1}{1 - ([\![a^*]\!] \times [\![b]\!])} \\ &= \frac{1}{1 - \left(\frac{1}{1 - [[a]]} \times z\right)} \\ &= \frac{1}{1 - \frac{z}{1 - z}} \\ &= \frac{1}{2} + \frac{1}{2 - 4 z} \end{align*}$

Ternyata, mengingat fungsi pembangkit di atas, ekstraksi koefisiennya akan menjadi

[z^{n}] [[(a^{*} b)^{*}]] = 2^{n - 1} + \frac{δ (n)}{2}

$[z^n][\![(a^*b)^*]\!] = 2^{n - 1} + \frac{\delta\left(n\right)}{2}$ dimana

δ (n) = {\begin{cases} 1 & if n = 0 \\ 0 & otherwise \end{cases}

$\delta(n) = \begin{cases} 1 & \text{if } n = 0 \\ 0 & \text{otherwise} \end{cases}$

Bahkan, sejak terjemahan kami $[\![\cdot]\!]$ menghasilkan fungsi rasional, kita dapat menggunakan dekomposisi fraksi parsial untuk membuat rumus enumerasi untuk setiap ekspresi reguler yang tidak ambigu.

Misalkan Anda memiliki fungsi rasional yang tidak dapat direduksi

r (z) + \frac{p (z)}{q (z)}

$r(z) + \frac{p(z)}{q(z)}$ dimana

r, p, q

$r, p, q$ adalah polinomial, maka Anda dapat menguraikannya menjadi

r (z) + \frac{C_{0}}{z - q_{0}^{*}} + \dots + \frac{C_{n}}{z - q_{n}^{*}}

$r(z) + \frac{C_0}{z - q^*_0} + \dots + \frac{C_n}{z - q^*_n}$ dimana

q_{k}^{*}

$q^*_k$ adalah akar dari

q (z)

$q(z)$ . Ada sedikit kasus sudut teknis (seperti banyaknya akar, dll), tetapi relatif mudah dilakukan ekstraksi koefisien pada ungkapan di atas:

[z^{n}] \frac{C}{z - q^{*}} = C \times {q^{*}}^{- n}

$[z^n] \frac{C}{z - q^*} = C \times {q^*}^{-n}$

Bahkan, dekomposisi fraksi parsial menggeneralisasi ke fungsi rasional multivariat, sehingga Anda benar-benar dapat membuat rumus penghitungan untuk kueri seperti "Berapa banyak kata yang ada di mana ada $n$ adan $m$ bs? "

Sayangnya, sejauh mana metode ini akan berguna berakhir ketika Anda memiliki ekspresi ambigu.

Lee
sumber

Mengapa tidak mudah untuk menghitung jumlah kata dalam bahasa biasa?

Jawaban: