Menemukan faktorisasi maksimal bahasa reguler

Biarkan bahasa $\mathcal{L} \subseteq \Sigma^*$ menjadi reguler.

Faktorisasi $\mathcal{L}$ adalah pasangan maksimal $(X,Y)$ dari kumpulan kata dengan

• $X \cdot Y \subseteq \mathcal{L}$
• $X \neq \emptyset \neq Y$ ,

dimana $X \cdot Y = \{xy$ | $x \in X, y \in Y\}$ .

$(X,Y)$ adalah maksimal jika untuk setiap pasangan$(X',Y') \neq (X,Y)$ dengan$X'\cdot Y' \subseteq \mathcal{L}$ baik$X \not \subseteq X'$ atau$Y \not \subseteq Y'$ .

Apakah ada prosedur sederhana untuk mengetahui pasangan mana yang maksimal?

Contoh:

Biarkan $\mathcal{L} = \Sigma^∗ab \Sigma^∗$ . Himpunan $F = \{u, v, w\}$ dihitung:

• $u =(\Sigma^∗, \Sigma^∗ab\Sigma^∗)$

• $v = (\Sigma^∗a\Sigma^∗, \Sigma^∗b\Sigma^∗)$

• $w = (\Sigma^∗ab\Sigma^∗, \Sigma^∗)$

dimana .$\Sigma = \{a,b\}$

Contoh lain:

dan L = Σ ∗ a Σ Set faktorisasi F = { q , r , s , t } dengan$\Sigma = \{a, b\}$$\mathcal{L} = \Sigma^*a\Sigma$$F = \{q, r, s, t\}$

• $q = (\Sigma^*, \mathcal{L})$

• $r = (\Sigma^*a, \Sigma + \mathcal{L})$

• $s = (\Sigma^*aa, \epsilon + \Sigma + \mathcal{L})$

• $t = (\mathcal{L}, \epsilon + \mathcal{L})$

Seperti yang disarankan dalam komentar untuk pertanyaan, saya akan mencoba memberikan (sayangnya sebagian) jawaban untuk pertanyaan itu, setidaknya sejauh saya telah memahami masalahnya sendiri (ini menyiratkan bahwa Anda mungkin menemukan kesalahan, dan jika Anda menemukan cara untuk menjelaskan secara lebih singkat atau jelas salah satu poin di bawah ini, jangan ragu untuk mengedit jawabannya):

Pertama, kita harus perhatikan bahwa kita tidak benar-benar harus menghitung otomat universal suatu bahasa jika kita ingin menghitung faktorisasi suatu bahasa.

Dari makalah yang disebutkan dalam komentar saya ¹, ada korespondensi 1-1 antara faktor kiri dan kanan bahasa biasa, yaitu, mengingat faktor kiri bahasa, faktor kanan yang sesuai ditentukan secara unik dan sebaliknya. Lebih tepatnya, kami memiliki yang berikut:

Mari menjadi faktorisasi L . Kemudian Y = ⋂ x ∈ X x - 1 L , X = ⋂ y ∈ Y L y - 1 , yaitu, setiap faktor kiri adalah persimpangan dari quotients kanan, dan setiap faktor kanan adalah persimpangan quotients kiri. Sebaliknya, setiap persimpangan quotients kiri L adalah faktor hak L , dan setiap persimpangan quotients kanan L adalah faktor kiri L .$(X,Y)$$L$

Perhatikan bahwa untuk bahasa reguler, hanya ada seperangkat terbatas negosiasi kiri dan kanan, dan dengan demikian atau masalah berkurang untuk menghitung negosiasi kiri dan kanan bahasa, dan kemudian menghitung -stable closure mereka, yaitu minimal superset dari quotients yang ditutup di bawah persimpangan. Ini kemudian justru faktor yang tepat dan faktor kiri, dan kemudian biasanya mudah untuk melihat mana pasangan adalah subset dari L .$\cap$$L$

Contoh

Untuk mengilustrasikan poin-poin di atas, perhatikan contoh pertama dalam pertanyaan (yang menurut saya juga tidak benar di koran):

Biarkan . Sekarang, quotients kiri L adalah set x - 1 L untuk x ∈ Σ * , yaitu, kata-kata u di Σ * yang dapat diawali dengan x , yaitu x u ∈ L . Kapan y - 1 L = x - 1 L untuk perbedaan x , y ? Ini adalah kasus jika dan hanya jika $L = \Sigma^\ast ab \Sigma^\ast$$L$$x^{-1}L$$x\in \Sigma^\ast$$u$$\Sigma^\ast$$x$$xu \in L$$y^{-1}L=x^{-1}L$$x,y$$x$dan dapat ditambahkan ke kata-kata dalam L dengan sufiks yang persis sama. Ini berarti, untuk memasukkannya ke dalam istilah yang lebih akrab, mereka adalah Nerode-equivalen, dan sufiks yang diperlukan untuk menambahkan kata-kata dalam kelas Nerode adalah tepatnya quotient kiri masing-masing.$y$$L$

Untuk , kita melihat bahwa kelas Nerode-equivalence kami$L$

• , himpunan kata-kata tidak mengandung sebuah b sebagai faktor dan berakhir dengan sebuah , $N_1$$ab$$a$
• , himpunan kata-kata yang berakhir dengan b dan tidak mengandung sebuah b sebagai faktor, dan $N_2$$b$$ab$
• , set kata-kata yang mengandung sebuah b sebagai faktor, yaitu, N 3 = $N_3$$ab$$N_3 = L$

Mereka dapat ditambah dengan set-set berikut (yaitu, ini adalah negosiasi kiri dari kata-kata di kelas masing-masing):

• untuk x di N 1 terdiri dari semua kata-kata dalam L (kata apapun dapat ditambah dengan kata yang berisi sebuah b sebagai faktor dan dengan demikian menjadi sebuah kata dalam L ) dan b Σ * , yaitu S 1 = L ∪ b Σ $S_1 = x^{-1}L$$x$$N_1$$L$$ab$$L$$b\Sigma^\ast$$S_1 = L \cup b\Sigma^\ast$
• untuk x dalam N 2 adalah bahasa itu sendiri, yaitu, S 2 = L dan$S_2 = x^{-1}L$$x$$N_2$$S_2 = L$
• untuk x dalam N 3 jelas Σ ∗ . Artinya, kami telah menemukan tiga faktor kanan L . Seperti S 2 ⊂ S 1 ⊂ S 3 ,penutupan ∩ - stabil merekaadalah S 1 , S 2 , S 3 , dan itu adalah faktor yang tepat.$S_3 = x^{-1}L$$x$$N_3$$\Sigma^\ast$$L$$S_2\subset S_1\subset S_3$$\cap$${S_1,S_2,S_3}$

Hence, our factorization set $\mathcal{F}_L$ is of the form $(P_1,S_1),(P_2,S_2),(P_3,S_3)$.

Now, for the left factors $P_i$, we use the equations of the beginning of this answer:

For $P_1$, this yields $L \cup \Sigma^\ast a$, for $P_2$ we get $\Sigma^\ast$ and for $P_3$, we obtain $L$. You can see this by inspection (the most popular excuse for being too lazy to state a formal proof) or by explicitly computing the right quotients (which is fairly analogous, although not completely, to computing the left quotients). Our factorizations are thus given by $\mathcal{F}_L = {u,v,w}$ where

• $u = (P_1,S_1) = (\Sigma^\ast ab \Sigma^\ast \cup \Sigma^\ast a, \Sigma^\ast ab \Sigma^\ast \cup b\Sigma^\ast)$
• $v = (P_2, S_2) = (\Sigma^\ast, \Sigma^\ast ab \Sigma^\ast)$ and
• $w = (P_3, S_3) = (\Sigma^\ast ab \Sigma^\ast, \Sigma^\ast)$

Summary

To summarize (as you were asking for a simple procedure):

• For computing the factorizations of a language $L$, first compute the left quotients of $L$.
• You can do so, in the language of the paper, by constructing a minimal DFA $A$ for $L$ and then for each state $q$ in $A$ (corresponding, as a Nerode-equivalence class, to a left quotient) compute the future of $q$ in $A$, thus obtaining one left quotient of the language for each state.
• The collection of left quotients obtained in this way yields, in general, a subset $S_R$ of the right factors.
• Compute then the $\cap$-stable closure of $S_R$, which can be done in practice by forming the intersection of any subset of $S_R$ and adding any subset obtained in this way to $S_R$.
• The set $S_R$ together with all the intersections from the previous step is then the set of right factors of $L$.
• In order to obtain the left factors, we can compute the right quotients of $L$.
• These are sets of the form $Ly^{-1}$, for $y\in \Sigma^\ast$. Now, these are again only finitely many, and for $x\neq y$, we have $Ly^{-1} = Lx^{-1}$ if and only if for all $u\in \Sigma^\ast$, $ux \in L \Leftrightarrow uy \in L$, that is they can be prefixed to words in the language with precisely the same set of strings.
• To compute $Lx^{-1}$, consider those states $q$ in $A$ such that $x$ is contained in the future of $q$. The union of the pasts of those states constitute one right quotient. Find all these quotients.
• You know you are done when you have found as many left factors as you have right factors.
• Find those pairs of left and right factors $X,Y$ such that $X\cdot Y \subseteq L$. This is $\mathcal{F}_L$.

1. The Universal Automaton by Lombardy and Sakarovitch (in Texts in Logic and Games, Vol 2: Logic and Automata: History and Perspectives, 2007)