Kuinka muuntaa äärelliset automaatit säännöllisiksi lausekkeiksi?
On helmikuu 16, 2021 by adminSäännöllisten lausekkeiden muuntaminen (minimaalisiksi) NFA: ksi, jotka hyväksyvät saman kielen, on helppoa tavallisilla algoritmeilla, esim. Thompsonin algoritmi . Toinen suunta näyttää kuitenkin olevan ikävämpi, ja joskus tuloksena olevat lausekkeet ovat sotkuisia.
Mitä algoritmit ovat onko NFA muunnettava vastaaviksi säännöllisiksi lausekkeiksi? Onko aikojen monimutkaisuuteen tai tuloksen kokoon liittyviä etuja?
Tämän oletetaan olevan referenssikysymys. Liitä mukaan menetelmäsi yleinen kuvaus ja ei-triviaali esimerkki.
Kommentit
- Huomaa samanlainen -kysymys osoitteessa cstheory.SE , joka ei todennäköisesti sovellu yleisöömme.
- kaikissa vastauksissa käytetään muodollista tekniikkaa RE: n kirjoittamiseen DFA: sta. Uskon, että tekniikkani analyysillä on suhteellisen helppoa ja objektiivista, osoitan vastauksessani : Mikä on tämän deterministisen äärellisen automaatin kieli? Minusta on joskus hyödyllistä. Kyllä, tietysti joskus käytän itse muodollista menetelmää (Ardenin lause) kirjoittaa RE on kysymys on monimutkainen, kuten tässä esimerkissä: Kuinka kirjoittaa säännöllinen lauseke DFA: lle
Vastaus
Muunnos äärellisistä automaateista säännöllisiin lausekkeisiin on useita. Tässä kuvaan sitä, mitä yleensä koulussa opetetaan, mikä on hyvin visuaalista. Uskon, että sitä käytetään käytännössä eniten. Algoritmin kirjoittaminen ei kuitenkaan ole kovin hyvä idea.
Tilanpoistomenetelmä
Tämä algoritmi koskee automaatin kaavion käsittelyä, eikä se siksi sovellu kovin hyvin algoritmeihin, koska se tarvitsee graafin primitiivit, kuten … valtion poisto. Kuvailen sitä korkeamman tason primitiivien avulla.
Ajatus
Ajatuksena on harkita säännöllisiä lausekkeita reunoilla ja poistaa sitten välitilat pitäen reunatarrat yhtenäisinä.
Pääkuvio näkyy seuraavassa kuvissa. Ensimmäisessä on tunnisteet $ p, q, r $, jotka ovat säännöllisiä lausekkeita $ e, f, g, h, i $, ja haluamme poistaa $ q $.
Kun se on poistettu, säveltämme $ e, f, g, h, i $ yhdessä (säilyttäen muut reunat $ p $: n ja $ r $: n välillä, mutta tätä ei näytetä tästä):
Esimerkki
Käytä samaa esimerkkiä kuin kohdassa Raphaelin vastaus :
poistamme $ q_2 $ peräkkäin:
ja sitten $ q_3 $:
meidän on silti sovellettava tähti lausekkeeseen $ q_1 $ – $ q_1 $. Tässä tapauksessa lopullinen tila on myös alkukirjain, joten meidän on vain lisättävä tähti:
$$ (ab + (b + aa) (ba) ^ * (a + bb)) ^ * $$
Algoritmi
L[i,j]
on kielen regekspi välillä $ q_i $ – $ q_j $. Ensinnäkin poistamme kaikki ti-reunat:
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
Nyt tila poistetaan. Oletetaan, että haluamme poistaa tilan $ q_k $:
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]
Huomaa, että sekä paperikynällä että algoritmilla sinun tulisi yksinkertaistaa lausekkeita, kuten star(ε)=ε
, e.ε=e
, ∅+e=e
, ∅.e=∅
(Kirjoittaja käsi et vain kirjoita reunaa, kun se ei ole $ ∅ $, tai edes $ ε $ itsesilmukalle, ja ohitat, kun $ q_i $: n ja $ q_k $: n tai $ q_j $: n ja $: n välillä ei ole siirtymää q_k $)
Kuinka nyt remove(k)
käytetään? Sinun ei pitäisi poistaa lopullisia tai alkutiloja kevyesti, muuten menetät kielen osia.
for i = 1 to n: if not(final(i)) and not(initial(i)): remove(i)
Jos sinulla on vain yksi lopullinen tila $ q_f $ ja yksi alkutila $ q_s $, lopullinen lauseke on:
e := star(L[s,s]) . L[s,f] . star(L[f,s] . star(L[s,s]) . L[s,f] + L[f,f])
Jos sinulla on useita lopputiloja (tai jopa alkutiloja), ei ole yksinkertaista tapaa yhdistää nämä paitsi transitiivisen sulkemismenetelmän soveltaminen. Yleensä tämä ei ole ongelma käsin, mutta se on hankalaa algoritmia kirjoitettaessa. Paljon yksinkertaisempi ratkaisu on luetella kaikki parit $ (s, f) $ ja suorittaa algoritmi (jo tilasta poistettu) kaaviossa saadaksesi kaikki lausekkeet $ e_ {s, f} $ olettaen, että $ s $ on ainoa alkutila ja $ f $ on ainoa lopullinen tila, joka tekee sitten kaikkien $ e_ {s, f} $: n yhdistämisen.
Tämä ja se, että tämä muuttaa kieliä dynaamisemmin kuin ensimmäinen menetelmä, tekevät siitä enemmän virhealtista ohjelmoinnissa. Ehdotan minkä tahansa muun menetelmän käyttämistä.
Miinukset
Tässä algoritmissa on paljon tapauksia, esimerkiksi poistettavan solmun valitseminen, lopputilojen lukumäärä lopussa , se tosiasia, että lopullinen tila voi olla myös alkutila. jne.Vain käytön konteksti on erilainen. En suosittele algoritmin käyttöönottoa, mutta menetelmän käyttäminen sen tekemiseen käsin on hyvä idea.
kommentit
- Esimerkissä 2. kuva, solmun poistamisen jälkeen ” 2 ”, solmusta A puuttuu reuna – silmukan reuna (ab).
- @Kabamaru: Kiinteä. Mutta nyt mielestäni kolmannen kuvan $ \ varepsilon $: n tulisi olla
ab
ja vastaavasti ehkä viimeisessä säännöllisessä lausekkeessa. - Voit tehdä algoritmin toimi minkä tahansa määrän alku- ja lopputiloja varten lisäämällä uusi alkuosa $ q ^ + $ ja uusi lopputila $ q ^ – $ ja yhdistämällä nämä alkuperäisiin alku- ja lopputiloihin $ \ varepsilon $ -reunoilla. Poista nyt kaikki alkuperäiset tilat. Lauseke löytyy sitten yhdestä jäljellä olevasta reunasta välillä $ q ^ + $ – $ q _- $. Rakenne ei anna silmukoita $ q ^ + $ tai $ q _- $, koska näillä tiloilla ei ole sisääntuloa tai. lähtevät reunat. Tai jos olet tiukka, heillä on tarroja, jotka edustavat tyhjää joukkoa.
- Toisessa esimerkissä on edelleen ongelma: ennen yksinkertaistamista automaatit hyväksyvät ” ba ”, (1, 3, 1), mutta yksinkertaistamisen jälkeen se ei ’ t.
Vastaus
Menetelmä
Kaikkein mukavin menetelmä, jonka olen nähnyt, ilmaisee automaatin (tavallisten) kielten yhtälöjärjestelmänä, joka voi ratkaista. Se on erityisen mukavaa, koska se näyttää tuottavan suppeampia lausekkeita kuin muut menetelmät.
Anna $ A = (Q, \ Sigma, \ delta, q_0, F) $ NFA ilman $ \ varepsilon $ – siirtymät. Luo jokaiselle osavaltiolle $ q_i $ kaava
$ \ qquad \ displaystyle Q_i = \ bigcup \ limits_ {q_i \ overset {a} {\ to} q_j} aQ_j \ cup \ begin {cases} \ {\ varepsilon \} &, \ q_i \ F: ssä \\ \ tyhjentöt &, \ text {else} \ end {cases} $
jossa $ F $ on lopullisten tilojen joukko ja $ q_i \ overset {a} {\ to} q_j $ tarkoittaa, että siirtyminen $ q_i $: sta $ q_j $: iin on merkitty $ a $: lla . Jos luet $ \ cup $ muodossa $ + $ tai $ \ mid $ (säännöllisen lausekkeen määritelmästä riippuen), huomaat, että tämä on säännöllisten lausekkeiden yhtälö.
Järjestelmän ratkaisemiseen tarvitaan assosiatiivisuutta. ja $ \ cup $: n ja $ \ cdot $: n (merkkijonon ketjutus) jakelu, $ \ cup $: n ja Ardenin Lemma ¹: n kommutatiivisuus:
Anna $ L, U, V \ subseteq \ Sigma ^ * $ tavallisten kielten kanssa $ \ varepsilon \ notin U $. Sitten
$ \ qquad \ displaystyle L = UL \ cup V \ quad \ Longleftrightarrow \ quad L = U ^ * V $
Ratkaisu on joukko säännöllisiä lausekkeita $ Q_i $, yksi jokaiselle osavaltiolle $ q_i $. $ Q_i $ kuvaa tarkalleen ne sanat, jotka $ A $ voi hyväksyä aloittaessaan $ q_i $: ssa; siksi $ Q_0 $ (jos $ q_0 $ on alkutila) on haluttu lauseke.
Esimerkki
Selkeyden vuoksi merkitsemme yksittäisjoukkoja niiden elementillä, eli $ a = \ {a \} $. esimerkki johtuu Georg Zetzschestä.
Harkitse t hänen NFA:
[ lähde ]
Vastaava yhtälöjärjestelmä on:
$ \ qquad \ begin {tasaus} Q_0 & = aQ_1 \ cup bQ_2 \ kuppi \ varepsilon \\ Q_1 & = bQ_0 \ kuppi aQ_2 \\ Q_2 & = aQ_0 \ kuppi bQ_1 \ loppu {tasaus} $
Liitä nyt kolmas yhtälö toiseen:
$ \ qquad \ begin {tasaa} Q_1 & = bQ_0 \ cup a (aQ_0 \ cup bQ_1) \\ & = abQ_1 \ cup (b \ cup aa) Q_0 \\ & = (ab) ^ * ( b \ cup aa) Q_0 \ end {align} $
Viimeisessä vaiheessa käytämme Ardenin lemmaa, jossa on $ L = Q_1 $, $ U = ab $ ja $ V = (b \ cup aa) \ cdot Q_0 $. Huomaa, että kaikki kolme kieltä ovat säännöllisiä ja $ \ varepsilon \ notin U = \ {ab \} $, mikä antaa meille mahdollisuuden soveltaa lemmaa. Nyt liitämme tämän tuloksen ensimmäiseen yhtälöön:
$ \ qquad \ begin {align} Q_0 & = a (ab) ^ * (b \ cup aa ) Q_0 \ cup baQ_0 \ cup bb (ab) ^ * (b \ cup aa) Q_0 \ cup \ varepsilon \\ & = ((a \ cup bb) (ab) ^ * (b \ cup aa) \ cup ba) Q_0 \ cup \ varepsilon \\ & = ((a \ cup bb) (ab) ^ * (b \ cup aa) \ cup ba) ^ * \ qquad \ text {(kirjoittanut Arden ”s Lemma)} \ end {tasaa} $
Siksi olemme löytäneet säännöllisen lausekkeen yllä olevan automaatin hyväksymälle kielelle, nimittäin
$ \ qquad \ displaystyle ((a + bb) (ab) ^ * (b + aa) + ba) ^ *. $
Huomaa, että se on melko ytimekäs (vertaa muiden menetelmien tulos), mutta niitä ei ole määritelty yksiselitteisesti; yhtälöjärjestelmän ratkaiseminen eri käsittelyjärjestyksellä johtaa muihin – vastaaviin! – lausekkeisiin.
- Ardenin todistamiseksi ” s Lemma, katso täältä .
kommentit
- mitä onko tämän algoritmin aika monimutkainen? Onko tuotetun lausekkeen koko sidottu?
- @jmite: Minulla ei ole aavistustakaan. En usko ’ uskoakseni ’ pyrkivän toteuttamaan tämän (muut menetelmät näyttävät olevan tässä suhteessa toteuttamiskelpoisempia), mutta käytän sitä kynä ja paperi -menetelmä.
- Tässä ’ sa tämän algoritmin Prolog-toteutus: github.com / wvxvw / intro-to-automata-theory / blob / master / automata / … , mutta sen
maybe_union/2
-edikaatti voisi käyttää enemmän työtä (esim. wrt eliminoimalla yhteisen etuliitteen) tehdäksesi siistimpiä säännöllisiä lausekkeita. Toinen tapa nähdä tämä menetelmä on ymmärtää se käännökseksi regexistä oikean lineaariseen kielioppiin, jossa kielet, joilla on Prolog-tyyppinen yhtenäisyys tai ML-tyyppinen kuvion sovitus, tekevät erittäin hyvistä muuntimista, joten ’ ei vain kynä-paperi-algoritmi 🙂 - Vain yksi kysymys. Ensimmäisen yhtälön ε johtuu siitä, että Qo on lähtötila tai koska se ’ on lopullinen tila? Samalla tavalla, jos minulla on kaksi lopputilaa, sovelletaan?
- @PAOK Tarkista $ Q_i $: n määritelmä yllä (rivi); se ’ s, koska $ q_0 $ on lopullinen tila.
Vastaa
Brzozowskin algebrallinen menetelmä
Tämä on sama menetelmä kuin joka on kuvattu Raphaelin vastauksessa , mutta näkymä systemaattisesta algoritmista ja sitten todellakin, algoritmi. Osoittautuu helpoksi ja luonnolliseksi toteuttaa, kun tiedät mistä aloittaa. Se voi myös olla helpompaa käsin, jos kaikkien automaattien piirtäminen on jostain syystä epäkäytännöllistä. / p>
Kun kirjoitat algoritmia, sinun on muistettava, että yhtälöiden on oltava aina lineaarisia, jotta sinulla on hyvä abstrakti esitys yhtälöistä, mikä voit unohtaa ratkaistessasi käsin.
Algoritmin idea
En kuvaile sen toimintaa, koska se on hyvin tehty Raphaelin vastauksessa , jonka minä ehdotan lukea ennen. Sen sijaan keskityn siihen, missä järjestyksessä sinun pitäisi ratkaista yhtälöt tekemättä liikaa ylimääräistä yhteistyötä mputoinnit tai ylimääräiset tapaukset.
Alkaen Ardenin säännön nerokas ratkaisu $ X = A ^ * B $ kielen yhtälöön $ X = AX∪B $ voimme pitää automaattia muodon yhtälöryhmänä:
$$ X_i = B_i + A_ {i, 1} X_1 +… + A_ {i, n} X_n $$
voimme ratkaista tämän indusoimalla $ n $ päivittämällä taulukot $ A_ {i, j} $ ja $ B_ {i, j} $ vastaavasti. Vaiheessa $ n $ meillä on:
$$ X_n = B_n + A_ {n, 1} X_1 +… + A_ {n, n} X_n $$
ja Ardenin sääntö antaa meille:
$$ X_n = A_ {n, n} ^ * (B_n + A_ {n, 1} X_1 +… + A_ {n, n-1} X_ {n -1}) $$
ja asettamalla $ B ”_n = A_ {n, n} ^ * B_n $ ja $ A” _ {n, i} = A_ {n, n} ^ * A_ {n, i} $ saamme:
$$ X_n = B ”_n + A” _ {n, 1} X_1 +… + A ”_ {n, n-1} X_ {n -1} $$
ja voimme sitten poistaa kaikki järjestelmän $ X_n $ tarpeet asettamalla arvoksi $ i, j < n $:
$$ B ”_i = B_i + A_ {i, n} B” _n $$ $$ A ”_ {i, j} = A_ {i, j} + A_ {i, n} A ”_ {n, j} $$
Kun $ X_n $ on ratkaistu, kun $ n = 1 $, saadaan seuraava yhtälö:
$$ X_1 = B” _1 $$
ilman $ A ”_ {1, i} $. Näin saimme säännöllisen lausekkeemme.
Algoritmi
Tämän ansiosta voimme rakentaa algoritmin. Saadaksemme saman käytännön kuin yllä olevassa induktiossa, sanomme, että alkutila on $ q_1 $ ja että tilan lukumäärä on $ m $. Ensin alustetaan $ B $: n täyttäminen:
for i = 1 to m: if final(i): B[i] := ε else: B[i] := ∅
ja $ 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] := ∅
ja sitten ratkaisu:
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]
lopullinen lauseke on sitten:
e := B[1]
Toteutus
Vaikka se saattaa tuntua yhtälöjärjestelmästä, joka näyttää liian symboliselta algoritmille, tämä soveltuu hyvin toteutukseen. Tässä on tämän algoritmin toteutus Ocamlissa (rikkinäinen linkki) . Huomaa, että funktion brzozowski
lisäksi kaikki on tulostettava tai käytettävä Raphaelin esimerkissä. Huomaa, että säännöllisten lausekkeiden .
Kommentit
- Linkki on kuollut …
- Käyttöönotto Javascriptissa: github.com/devongovett/regexgen/blob/master/src/regex.js
- Kiitos tästä upeasta selityksestä. Jos ymmärrän oikein, alustuspseudokoodisi olettaa, että tietyille i: lle ja j: lle on enintään yksi sellainen, että (i, a, j) on siirtymä.Tämä on oikein, jos suostumme merkitsemään tämän siirtymän regeksillä, joka vastaa kaikkia Σ että etiketti siirtyy i: stä j: iin kirjainautomaatissa, mutta merkintä a in Σ on hieman outo, koska se ei oikeastaan ole kirjainta. Jos siirrymme kirjaimelta kirjaimelle, meillä voi olla useita siirtymiä i: stä j: hen ja meidän on tee tarrojen liitos silmukan rungossa.
Vastaus
Transitiivinen sulkemismenetelmä
Tätä menetelmää on helppo kirjoittaa muodossa algoritmia, mutta tuottaa järjettömän suuria säännöllisiä lausekkeita ja on epäkäytännöllistä, jos teet sen käsin, lähinnä siksi, että tämä on liian järjestelmällistä. Se on kuitenkin hyvä ja yksinkertainen ratkaisu algoritmille.
Keskeinen ajatus
Olkoon $ R ^ k_ {i, j} $ $ -merkkijonojen säännöllinen lauseke. q_i $ – $ q_j $ käyttäen osavaltioita $ \ {q_1,…, q_k \} $. Olkoon $ n $ automaattin tilojen lukumäärä.
Oletetaan, että tiedät jo säännöllisen lausekkeen $ R_ {i, j} $ välillä $ q_i $ – $ q_j $ ilman välitilaa $ q_k $ (lukuun ottamatta ääripäitä), kaikille $ i, j $. Sitten voit arvata, kuinka toisen tilan lisääminen vaikuttaa uuteen säännölliseen lausekkeeseen $ R ”_ {i, j} $: se muuttuu vain, jos sinulla on suoria siirtymiä kohtaan $ q_k $, ja se voidaan ilmaista näin:
$$ R ”_ {i, j} = R_ {i, j} + R_ {i, k}. R_ {k, k} ^ *. R_ {k, j} $$
($ R $ on $ R ^ {k-1} $ ja $ R ”$ on $ R ^ k $.)
Esimerkki
Käytämme samaa esimerkkiä kuin Raphaelin vastauksessa . Aluksi voit käyttää vain suoria siirtymiä.
Tämä on ensimmäinen vaihe (huomaa, että itsesilmukka, jossa on tunniste $ a $, olisi muuttanut ensimmäisen $ ε $: n $ (ε + a) $.
$$ R ^ 0 = \ begin {bmatrix} ε & a & b \\ b & ε & a \\ a & b & ε \ end {bmatrix} $$
Toisessa vaiheessa voimme käyttää $ q_0 $ (joka nimetään meille uudeksi nimeksi $ q_1 $, koska $ R ^ 0 $ käytetään jo yllä oleva tarkoitus). Näemme, kuinka $ R ^ 1 $ toimii.
$ q_2 $ – $ q_2 $: $ R ^ 1_ {2,2} = R ^ 0_ {2,2} + R ^ 0_ {2,1} {R ^ 0_ {1,1}} ^ * R ^ 0_ {1,2} = ε + b ε ^ * a = ε + ba $.
Miksi niin? Se johtuu siitä, että siirtyminen $ q_2 $: sta $ q_2 $: iin käyttämällä vain $ q_1 $: ta välitilana voidaan tehdä pysymällä täällä ($ ε $) tai menemällä kohtaan $ q_1 $ ($ a $), silmukoiden siellä ($ ε ^ * $) ja palataan takaisin ($ b $).
$$ R ^ 1 = \ begin {bmatrix} ε & a & b \\ b & ε + ba & a + bb \\ a & b + aa & ε + ab \ end {bmatrix} $$
Voit laskea myös $ R ^ 2 $ ja $ R ^ 3 $ sekä $ R ^ 3_ {1,1 } $ antaa sinulle lopullisen lausekkeen, koska $ 1 $ on sekä alku- että loppulause. Huomaa, että tässä on tehty paljon lausekkeiden yksinkertaistamista. Muuten $ R ^ 0 $: n ensimmäinen $ a $ olisi $ (∅ + a) $ ja $ R ^ 1 $: n ensimmäinen $ a $ olisi $ ((∅ + a) + ε (ε) ^ * a ) $.
Algoritmi
Alustus:
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
Transitiivinen sulkeminen:
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)
Silloin lopullinen lauseke on (olettaen, että alkutila on $ q_s $):
e := ∅ for i = 1 to n: if final(i): e := e + R[s,i,n]
Mutta voitte kuvitella se tuottaa rumia säännöllisiä lausekkeita. Voit todellakin odottaa esimerkiksi $ (∅) ^ * + (a + (∅) ^ *) (ε) ^ * (a + ∅) $, joka edustaa samaa kieltä kuin $ aa $. Huomaa, että säännöllisen lausekkeen yksinkertaistamisesta on hyötyä käytännössä.
Vastaa