Bagaimana cara mengubah automata terbatas ke ekspresi reguler?


115

Mengubah ekspresi reguler menjadi (minimal) NFA yang menerima bahasa yang sama adalah mudah dengan algoritma standar, misalnya algoritma Thompson . Namun, arah yang lain tampaknya lebih membosankan, dan terkadang ekspresi yang dihasilkannya berantakan.

Algoritma apa yang ada untuk mengubah NFA menjadi ekspresi reguler yang setara? Apakah ada keuntungan terkait kompleksitas waktu atau ukuran hasil?

Ini seharusnya menjadi pertanyaan referensi. Harap sertakan uraian umum tentang metode Anda serta contoh yang tidak sepele.


2
Perhatikan pertanyaan serupa di cstheory.SE yang mungkin tidak cocok untuk audiens kami.
Raphael

semua jawaban menggunakan teknik formal untuk menulis RE dari DFA. Saya percaya teknik saya dengan analisis relatif mudah dan obyektif yang saya tunjukkan dalam jawaban saya: Apa bahasa dari automata terbatas deterministik ini? Saya merasa itu akan sangat membantu kapan-kapan. Ya, tentu saja kadang-kadang saya sendiri menggunakan metode formal (Arden theorem) untuk menulis RE adalah pertanyaan yang kompleks seperti yang diberikan dalam contoh ini: Bagaimana menulis ekspresi reguler untuk DFA
Grijesh Chauhan

Jawaban:


94

Ada beberapa metode untuk melakukan konversi dari automata terbatas ke ekspresi reguler. Di sini saya akan menjelaskan yang biasanya diajarkan di sekolah yang sangat visual. Saya percaya ini adalah yang paling banyak digunakan dalam praktik. Namun, menulis algoritme bukanlah ide yang bagus.

Metode penghapusan negara

Algoritma ini adalah tentang penanganan grafik automaton dan oleh karena itu sangat tidak cocok untuk algoritma karena perlu grafik primitif seperti ... penghapusan negara. Saya akan menggambarkannya menggunakan primitif tingkat tinggi.

Ide kuncinya

Idenya adalah untuk mempertimbangkan ekspresi reguler pada tepian dan kemudian menghapus negara perantara sambil menjaga label tepi konsisten.

Pola utama dapat dilihat pada gambar di bawah ini. Yang pertama memiliki label antara yang merupakan ekspresi reguler dan kami ingin menghapus .e , f , g , h , i qp,q,re,f,g,h,iq

otomat pqr

Setelah dihapus, kami menyusun bersamaan (sambil mempertahankan tepi lainnya antara dan tetapi ini tidak ditampilkan pada ini):p re,f,g,h,ipr

masukkan deskripsi gambar di sini

Contoh

Menggunakan contoh yang sama seperti dalam jawaban Raphael :

1-2-3 otomat

kami berhasil menghapus :q2

1-3 otomat

lalu :q3

1 robot

maka kita masih harus menerapkan bintang pada ekspresi dari hingga . Dalam hal ini, keadaan akhir juga awal sehingga kita benar-benar hanya perlu menambahkan bintang:q 1q1q1

(ab+(b+aa)(ba)?(a+bb))?

Algoritma

L[i,j]adalah regexp dari bahasa dari ke . Pertama, kami menghapus semua multi-edge:q jqiqj

for i = 1 to n:
  for j = 1 to n:
    if i == j then:
      L[i,j] := ε
    else:
      L[i,j] := ?
    for a in Σ:
      if trans(i, a, j):
        L[i,j] := L[i,j] + a

Sekarang, penghapusan status. Misalkan kita ingin menghapus status :qk

remove(k):
  for i = 1 to n:
    for j = 1 to n:
      L[i,i] += L[i,k] . star(L[k,k]) . L[k,i]
      L[j,j] += L[j,k] . star(L[k,k]) . L[k,j]
      L[i,j] += L[i,k] . star(L[k,k]) . L[k,j]
      L[j,i] += L[j,k] . star(L[k,k]) . L[k,i]

Perhatikan bahwa kedua dengan pensil kertas dan dengan algoritma Anda harus menyederhanakan ekspresi seperti star(ε)=ε, e.ε=e, ?+e=e, ?.e=?(Dengan tangan Anda hanya tidak menulis tepi ketika itu tidak , atau bahkan untuk diri loop dan Anda mengabaikan ketika ada tidak ada transisi antara dan atau dan )?q j q kεq kqiqkqjqk

Sekarang, bagaimana cara menggunakannya remove(k)? Anda tidak boleh menghapus status akhir atau awal dengan ringan, jika tidak, Anda akan kehilangan bagian bahasa.

for i = 1 to n:
  if not(final(i)) and not(initial(i)):
    remove(i)

Jika Anda hanya memiliki satu status akhir dan satu status awal maka ekspresi terakhirnya adalah:q sqfqs

e := star(L[s,s]) . L[s,f] . star(L[f,s] . star(L[s,s]) . L[s,f] + L[f,f])

Jika Anda memiliki beberapa keadaan akhir (atau bahkan keadaan awal) maka tidak ada cara sederhana untuk menggabungkan yang ini, selain menerapkan metode penutupan transitif. Biasanya ini bukan masalah dengan tangan tetapi ini aneh ketika menulis algoritma. Solusi yang jauh lebih sederhana adalah menghitung semua pasangan dan menjalankan algoritma pada grafik (sudah dihapus) untuk mendapatkan semua ekspresi seandainya adalah satu-satunya keadaan awal dan adalah satu-satunya final nyatakan, lalu lakukan penyatuan semua .e s , f s f e s , f(s,f)es,fsfes,f

Ini, dan fakta bahwa ini memodifikasi bahasa lebih dinamis daripada metode pertama membuatnya lebih rentan kesalahan saat pemrograman. Saya sarankan menggunakan metode lain.

Cons

Ada banyak kasus dalam algoritme ini, misalnya untuk memilih simpul mana yang harus kita hapus, jumlah keadaan akhir di akhir, fakta bahwa keadaan akhir dapat menjadi awal, juga dll.

Perhatikan bahwa sekarang setelah algoritme ditulis, ini sangat mirip dengan metode penutupan transitif. Hanya konteks penggunaannya yang berbeda. Saya tidak merekomendasikan menerapkan algoritma, tetapi menggunakan metode untuk melakukannya dengan tangan adalah ide yang bagus.


1
Dalam contoh, gambar ke-2, setelah menghapus simpul "2", ada tepi yang hilang - tepi loop (ab) di simpul A.
Panos Kal.

@ Kabamaru: Diperbaiki Tapi sekarang saya pikir pada gambar ke-3 juga seharusnya , dan mungkin juga dalam ekspresi reguler akhir. εab
Pengembaraan Logika

Anda dapat membuat algoritme berfungsi untuk sejumlah status awal dan akhir dengan menambahkan awal baru dan status akhir baru , dan menghubungkannya ke status awal dan akhir asli dengan -edges. Sekarang hapus semua status asli. Ekspresi kemudian ditemukan di tepi yang tersisa dari ke . Konstruksi tidak akan memberikan loop pada atau karena negara-negara ini tidak memiliki resp. tepi keluar. Atau jika Anda ketat, mereka akan memiliki label yang mewakili set kosong. q - ε q + q - q + q -q+q?εq+q?q+q?
Hendrik Jan

1
Masih ada masalah dengan contoh kedua: sebelum penyederhanaan automata menerima "ba", (1, 3, 1) tetapi setelah penyederhanaan tidak.
wvxvw

50

metode

Metode terbaik yang saya lihat adalah metode yang mengekspresikan otomat sebagai sistem persamaan bahasa (reguler) yang dapat diselesaikan. Ini khususnya bagus karena tampaknya menghasilkan ekspresi yang lebih ringkas daripada metode lain.

Biarkan sebuah NFA tanpa -transisi. Untuk setiap keadaan , buat persamaannyaA=(Q,Σ,δ,q0,F)εqi

Qi=?qiaqjaQj{{ε},?qiF?,?else

di mana adalah himpunan status akhir dan berarti ada transisi dari ke dengan label . Jika Anda membaca sebagai atau (tergantung pada definisi ekspresi reguler Anda), Anda melihat bahwa ini adalah persamaan dari ekspresi reguler.Fqiaqjqiqja+

Untuk menyelesaikan sistem, Anda memerlukan asosiatif dan distribusi dari dan (penggabungan string), komutatifitas dan 1:?

Biarkan bahasa reguler dengan . Kemudian,L,U,V?Σ?ε?U

L=ULV?L=U?V

Solusinya adalah seperangkat ekspresi reguler , satu untuk setiap negara . menguraikan dengan tepat kata-kata yang dapat diterima oleh ketika dimulai pada ; oleh karena itu (jika adalah kondisi awal) adalah ekspresi yang diinginkan.QiqiQiAqiQ0q0


Contoh

Demi kejelasan, kami menunjukkan set singleton oleh elemen mereka, yaitu . Contohnya adalah karena Georg Zetzsche.a={a}

Pertimbangkan NFA ini:

contoh nfa
[ sumber ]

Sistem persamaan yang sesuai adalah:

Q0=aQ1bQ2εQ1=bQ0aQ2Q2=aQ0bQ1

Sekarang hubungkan persamaan ketiga ke persamaan kedua:

Q1=bQ0a(aQ0bQ1)=abQ1(baa)Q0=(ab)?(baa)Q0

Untuk langkah terakhir, kami menerapkan Arden's Lemma dengan , dan . Perhatikan bahwa ketiga bahasa adalah reguler dan , memungkinkan kami untuk menerapkan lemma. Sekarang kita hubungkan hasil ini ke dalam persamaan pertama:L=Q1U=abV=(baa)?Q0ε?U={ab}

Q0=a(ab)?(baa)Q0baQ0bb(ab)?(baa)Q0ε=((abb)(ab)?(baa)ba)Q0ε=((abb)(ab)?(baa)ba)?(by Arden's Lemma)

Dengan demikian, kami telah menemukan ekspresi reguler untuk bahasa yang diterima oleh robot di atas, yaitu

((a+bb)(ab)?(b+aa)+ba)?.

Perhatikan bahwa ini cukup ringkas (bandingkan dengan hasil metode lain) tetapi tidak ditentukan secara unik; memecahkan sistem persamaan dengan urutan manipulasi yang berbeda mengarah ke yang lain - setara! - ekspresi.


  1. Untuk bukti Lemma Arden, lihat di sini .

1
Apa kompleksitas waktu dari algoritma ini? Apakah ada batasan ukuran ekspresi yang dihasilkan?
jmite

@iteite: Saya tidak tahu. Saya tidak berpikir saya akan mencoba menerapkan ini (metode lain tampaknya lebih layak dalam hal ini) tetapi menggunakannya sebagai metode pena-dan-kertas.
Raphael

1
Berikut ini adalah implementasi Prolog dari algoritma ini: github.com/wvxvw/intro-to-automata-theory/blob/master/automata/... tetapi maybe_union/2predikatnya dapat menggunakan lebih banyak pekerjaan (terutama awalan yang menghilangkan awalan umum) untuk membuat ekspresi reguler yang lebih rapi. Cara lain untuk melihat metode ini adalah memahaminya sebagai terjemahan dari regex ke tata bahasa linier-kanan, di mana bahasa dengan penyatuan seperti Prolog atau pencocokan pola seperti ML menghasilkan transduser yang sangat baik, sehingga bukan hanya pena-dan-kertas algoritme :)
wvxvw

Hanya satu pertanyaan. Ε dalam persamaan pertama adalah karena Qo adalah keadaan awal atau karena itu adalah keadaan akhir? Cara yang sama jika saya memiliki dua status akhir berlaku?
Georgio3

@ PAOK Periksa definisi atas (baris); itu karena adalah keadaan akhir. Qiq0
Raphael

28

Metode aljabar Brzozowski

Ini adalah metode yang sama dengan yang dijelaskan dalam jawaban Raphael , tetapi dari sudut pandang algoritma sistematis, dan kemudian, memang, algoritma tersebut. Ternyata menjadi mudah dan alami untuk diterapkan setelah Anda tahu harus mulai dari mana. Juga mungkin lebih mudah dengan tangan jika menggambar semua automata tidak praktis untuk beberapa alasan.

Saat menulis sebuah algoritma Anda harus ingat bahwa persamaan harus selalu linier sehingga Anda memiliki representasi abstrak yang baik dari persamaan, hal yang dapat Anda lupakan ketika Anda menyelesaikan dengan tangan.

Gagasan algoritma

Saya tidak akan menjelaskan cara kerjanya karena dilakukan dengan baik dalam jawaban Raphael yang saya sarankan untuk dibaca sebelumnya. Sebagai gantinya, saya fokus pada urutan mana Anda harus menyelesaikan persamaan tanpa melakukan terlalu banyak perhitungan ekstra atau kasus ekstra.

Mulai dari solusi cerdas peraturan Arden ke persamaan bahasa kita dapat mempertimbangkan otomat sebagai seperangkat persamaan bentuk:X=A?BX=AXB

Xi=Bi+Ai,1X1++Ai,nXn

kita dapat menyelesaikan ini dengan induksi pada dengan memperbarui array dan sesuai. Pada langkah , kita memiliki:nAi,jBi,jn

Xn=Bn+An,1X1++An,nXn

dan aturan Arden memberi kita:

Xn=An,n?(Bn+An,1X1++An,n?1Xn?1)

dan dengan mengatur dan kita dapatkan:Bn=An,n?BnAn,i=An,n?An,i

Xn=Bn+An,1X1++An,n?1Xn?1

dan kita kemudian dapat menghapus semua kebutuhan dalam sistem dengan mengatur, untuk :Xni,j<n

Bi=Bi+Ai,nBn
Ai,j=Ai,j+Ai,nAn,j

Ketika kami telah menyelesaikan ketika , kami memperoleh persamaan seperti ini:Xnn=1

X1=B1

tanpa . Jadi kami mendapatkan ekspresi reguler kami.A1,i

Algoritma

Berkat ini, kami dapat membangun algoritme. Untuk memiliki konvensi yang sama dari pada induksi di atas, kita akan mengatakan bahwa keadaan awal adalah dan bahwa jumlah keadaan adalah . Pertama, inisialisasi untuk mengisi :q1mB

for i = 1 to m:
  if final(i):
    B[i] := ε
  else:
    B[i] := ?

dan :A

for i = 1 to m:
  for j = 1 to m:
    for a in Σ:
      if trans(i, a, j):
        A[i,j] := a
      else:
        A[i,j] := ?

dan kemudian solusinya:

for n = m decreasing to 1:
  B[n] := star(A[n,n]) . B[n]
  for j = 1 to n:
    A[n,j] := star(A[n,n]) . A[n,j];
  for i = 1 to n:
    B[i] += A[i,n] . B[n]
    for j = 1 to n:
      A[i,j] += A[i,n] . A[n,j]

ekspresi terakhirnya adalah:

e := B[1]

Penerapan

Bahkan jika itu mungkin tampak suatu sistem persamaan yang tampaknya terlalu simbolis untuk suatu algoritma, yang satu ini sangat cocok untuk suatu implementasi. Berikut ini adalah implementasi dari algoritma ini di Ocaml (broken link) . Perhatikan bahwa selain fungsi brzozowski, semuanya untuk dicetak atau digunakan untuk contoh Raphael. Perhatikan bahwa ada fungsi penyederhanaan ekspresi reguler yang sangat efisien simple_re.


4
Tautan sudah mati ...
Columbo


24

Metode penutupan transitif

Metode ini mudah ditulis dalam bentuk algoritme, tetapi menghasilkan ekspresi reguler besar yang tidak masuk akal dan tidak praktis jika Anda melakukannya dengan tangan, terutama karena ini terlalu sistematis. Ini adalah solusi yang baik dan sederhana untuk suatu algoritma.

Ide kuncinya

Biarkan mewakili ekspresi reguler untuk string dari ke menggunakan status . Biarkan menjadi jumlah status otomat.Ri,jkqiqj{q1,,qk}n

Misalkan Anda sudah tahu ekspresi reguler dari ke tanpa status perantara (kecuali untuk ekstremitas), untuk semua . Maka Anda dapat menebak bagaimana menambahkan status lain akan memengaruhi ekspresi reguler baru : ia hanya berubah jika Anda memiliki transisi langsung ke , dan itu dapat diekspresikan seperti itu:Ri,jqiqjqki,jRi,jqk

Ri,j=Ri,j+Ri,k.Rk,k?.Rk,j

( adalah dan adalah .)RRk?1RRk

Contoh

Kami akan menggunakan contoh yang sama seperti dalam jawaban Raphael . Pada awalnya, Anda hanya dapat menggunakan transisi langsung.

Inilah langkah pertama (perhatikan bahwa loop otomatis dengan label akan mengubah pertama menjadi .aε(ε+a)

R0=[εabbεaabε]

Pada langkah kedua kita dapat menggunakan (yang diubah namanya menjadi untuk kita, karena sudah digunakan untuk tujuan di atas). Kita akan melihat bagaimana bekerja.q0q1R0R1

Dari ke : .q2q2R2,21=R2,20+R2,10R1,10?R1,20=ε+bε?a=ε+ba

Mengapa demikian? Itu karena pergi dari ke hanya menggunakan sebagai keadaan peralihan dapat dilakukan dengan tetap di sini ( ) atau pergi ke ( ), berputar-putar di sana ( ) dan kembali ( ).q2q2q1εq1aε?b

R1=[εabbε+baa+bbab+aaε+ab]

Anda dapat menghitung seperti itu dan juga, dan akan memberi Anda ekspresi akhir karena adalah awal dan akhir. Perhatikan bahwa banyak penyederhanaan ekspresi telah dilakukan di sini. Jika tidak pertama dari akan dan yang pertama dari akan menjadi .R2R3R1,131aR0(?+a)aR1((?+a)+ε(ε)?a)

Algoritma

Inisialisasi:

for i = 1 to n:
  for j = 1 to n:
    if i == j:
      R[i,j,0] := ε
    else:
      R[i,j,0] := ?
    for a in Σ:
      if trans(i, a, j):
        R[i,j,0] := R[i,j,0] + a

Penutupan transitif:

for k = 1 to n:
  for i = 1 to n:
    for j = 1 to n:
      R[i,j,k] := R[i,j,k-1] + R[i,k,k-1] . star(R[k,k,k-1]) . R(k,j,k-1)

Kemudian ekspresi terakhirnya adalah (seandainya adalah keadaan awal):qs

e := ?
for i = 1 to n:
  if final(i):
    e := e + R[s,i,n]

Tapi Anda bisa bayangkan itu menghasilkan ekspresi reguler jelek. Anda memang dapat mengharapkan hal-hal seperti yang mewakili bahasa yang sama dengan . Perhatikan bahwa menyederhanakan ekspresi reguler berguna dalam praktiknya.a a(?)?+(a+(?)?)(ε)?(a+?)aa

Dengan menggunakan situs kami, Anda mengakui telah membaca dan memahami Kebijakan Cookie dan Kebijakan Privasi kami.
Licensed under cc by-sa 3.0 with attribution required.
Judi bola