Menemukan faktorisasi maksimal bahasa reguler

13

Biarkan bahasa LΣ menjadi reguler.

Faktorisasi L adalah pasangan maksimal (X,Y) dari kumpulan kata dengan

  • XYL
  • XY ,

dimana XY={xy | xX,yY} .

(X,Y) adalah maksimal jika untuk setiap pasangan(X,Y)(X,Y) denganXYL baikXX atauYY .

Apakah ada prosedur sederhana untuk mengetahui pasangan mana yang maksimal?

Contoh:

Biarkan L=ΣabΣ . Himpunan F={u,v,w} dihitung:

  • u=(Σ,ΣabΣ)

  • v=(ΣaΣ,ΣbΣ)

  • w=(ΣabΣ,Σ)

dimana .Σ={a,b}

Contoh lain:

dan L = Σ a Σ Set faktorisasi F = { q , r , s , t } denganΣ={a,b}L=ΣaΣF={q,r,s,t}

  • q=(Σ,L)

  • r=(Σa,Σ+L)

  • s=(Σaa,ϵ+Σ+L)

  • t=(L,ϵ+L)

Laura
sumber
4
Saya merekomendasikan membaca makalah berikut (khususnya ayat 4.1) oleh Jacques Sakarovitch: perso.telecom-paristech.fr/ ~ jsaka
Cornelius Brand
1
Saya ingin tahu apakah Anda mungkin ingin lebih spesifik tentang masalahnya, yaitu kalimat terakhir dari pertanyaan Anda? Apakah kita diberi dan kita ingin menguji apakah ( X , Y ) sudah maksimal? Apakah tugas kita untuk menghitung semua ( X , Y ) yang maksimal? Jika yang terakhir, apakah jelas bahwa daftar ini berukuran atau polinomial? Mungkin tidak masuk akal untuk meminta algoritma untuk menghitung semua kemungkinan jika ada banyak dari mereka secara eksponensial. Juga, Anda ingin menentukan bagaimana bahasa L diwakili ketika disajikan kepada kami, dan bagaimana X , YX,Y(X,Y)(X,Y)LX,Ydiwakili? (mis. DFA, NFA, regexp)
DW
2
Saya tidak mengerti contoh Anda. Apakah seharusnya semua pasangan maksimal? v tampaknya tidak valid ...u,v,wv
Raphael
1
Contohnya diambil dari kertas yang disebutkan di atas. seharusnya pasangan maksimal. Saya juga tidak mengerti bagaimana v dihitung karena tampaknya belum tentu di L . Saya akan memposting contoh lain. u,v,wvL
Laura
1
@ Raphael, bagi saya sepertinya valid. Membiarkan X = Σ a Σ , Y = Σ b Σ , ( X , Y ) adalah faktorisasi, karena X Y = L (pertimbangkan sembarang string yang berisi a , lalu urutan a dan / atau b 's, kemudian akhirnya sebuah b : string ini harus memiliki beberapa titik di mana yang pertama b muncul, sehingga merupakan titik di mana mengandung suatuvX=ΣaΣY=ΣbΣ(X,Y)XY=Laabbb ). Saya tidak punya bukti bahwa itu adalah maksimal, tapi saya tidak dapat menemukan yang lebih besar set X ' , Y ' yang merupakan faktorisasi L . abX,YL
DW

Jawaban:

8

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

Y=xXx1L,X=yYLy1,
LLLL

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 .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 xL=ΣabΣLx1LxΣuΣxxuLy1L=x1Lx,yxdan 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.yL

Untuk , kita melihat bahwa kelas Nerode-equivalence kamiL

  • , himpunan kata-kata tidak mengandung sebuah b sebagai faktor dan berakhir dengan sebuah , N1aba
  • , himpunan kata-kata yang berakhir dengan b dan tidak mengandung sebuah b sebagai faktor, dan N2bab
  • , set kata-kata yang mengandung sebuah b sebagai faktor, yaitu, N 3 = LN3abN3=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 Σ S1=x1LxN1LabLbΣS1=LbΣ
  • untuk x dalam N 2 adalah bahasa itu sendiri, yaitu, S 2 = L danS2=x1LxN2S2=L
  • untuk x dalam N 3 jelas Σ . Artinya, kami telah menemukan tiga faktor kanan L . Seperti S 2S 1S 3 ,penutupan - stabil merekaadalah S 1 , S 2 , S 3 , dan itu adalah faktor yang tepat.S3=x1LxN3ΣLS2S1S3S1,S2,S3

Hence, our factorization set FL is of the form (P1,S1),(P2,S2),(P3,S3).

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

Pi=xSiLx1
.

For P1, this yields LΣa, for P2 we get Σ and for P3, 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 FL=u,v,w where

  • u=(P1,S1)=(ΣabΣΣa,ΣabΣbΣ)
  • v=(P2,S2)=(Σ,ΣabΣ) and
  • w=(P3,S3)=(ΣabΣ,Σ)

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 SR of the right factors.
  • Compute then the -stable closure of SR, which can be done in practice by forming the intersection of any subset of SR and adding any subset obtained in this way to SR.
  • The set SR 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 Ly1, for yΣ. Now, these are again only finitely many, and for xy, we have Ly1=Lx1 if and only if for all uΣ, uxLuyL, that is they can be prefixed to words in the language with precisely the same set of strings.
  • To compute Lx1, 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 XYL. This is FL.

  1. The Universal Automaton by Lombardy and Sakarovitch (in Texts in Logic and Games, Vol 2: Logic and Automata: History and Perspectives, 2007)
Cornelius Brand
sumber
3
Nice! Let's note that AB is decidable for regular languages and that these factors X, Y end up being regular due to closure properties. Hence we can not only effectively compute the last bullet in the summary, but we can also filter out the maximal pairs.
Raphael