Hvordan konvertere endelige automata til regulære uttrykk?
On februar 16, 2021 by adminKonvertering av regulære uttrykk til (minimal) NFA som aksepterer samme språk er enkelt med standardalgoritmer, f.eks. Thompsons algoritme . Den andre retningen ser ut til å være mer kjedelig, og noen ganger er de resulterende uttrykkene rotete.
Hva algoritmer er der for å konvertere NFA til tilsvarende regulære uttrykk? Er det fordeler med hensyn til tidskompleksitet eller resultatstørrelse?
Dette skal være et referansespørsmål. Ta med en generell beskrivelse av metoden din samt en ikke-trivielt eksempel.
Kommentarer
- Legg merke til et lignende spørsmål over kl. cstheory.SE , som sannsynligvis ikke passer for publikum.
- Alle svar bruker formell teknikk for å skrive RE fra DFA. Jeg tror teknikken min ved analyse er relativt enkel og objektiv jeg demonstrerer i mitt svar : Hva er språket til denne deterministiske endelige automaten? Jeg føler at det vil være nyttig en gang. Ja, selvfølgelig bruker jeg selv formell metode (Arden-teorem) å skrive RE er spørsmålet er komplekst som gitt i dette eksemplet: Hvordan skrive vanlig uttrykk for en DFA
Svar
Det er flere metoder for å gjøre konverteringen fra endelige automata til regulære uttrykk. Her vil jeg beskrive den som vanligvis undervises i skolen, som er veldig visuell. Jeg tror det er det mest brukte i praksis. Å skrive algoritmen er imidlertid ikke så god ide.
Tilstandsfjerningsmetode
Denne algoritmen handler om å håndtere grafen til automaten og er dermed ikke veldig egnet for algoritmer siden den trenger primitiver som … tilstandsfjerning. Jeg vil beskrive det ved hjelp av primitiver på høyere nivå.
Nøkkelideen
Ideen er å vurdere regelmessige uttrykk på kanter og deretter fjerne mellomtilstander mens kantene blir etiketter konsistente.
Hovedmønsteret kan sees i figurene nedenfor. Den første har etiketter mellom $ p, q, r $ som er regulære uttrykk $ e, f, g, h, i $, og vi vil fjerne $ q $.
Når vi først er fjernet, komponerer vi $ e, f, g, h, i $ sammen (mens vi holder de andre kantene mellom $ p $ og $ r $, men dette vises ikke på dette):
Eksempel
Bruk samme eksempel som i Raphaels svar :
vi fjerner suksessivt $ q_2 $:
og deretter $ q_3 $:
så må vi fremdeles bruke en stjerne på uttrykket fra $ q_1 $ til $ q_1 $. I dette tilfellet er den endelige tilstanden også innledende, så vi trenger egentlig bare å legge til en stjerne:
$$ (ab + (b + aa) (ba) ^ * (a + bb)) ^ * $$
Algoritme
L[i,j]
er regexp for språket fra $ q_i $ til $ q_j $. Først fjerner vi alle mul ti-kanter:
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
Nå er statens fjerning. Anta at vi vil fjerne staten $ 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]
Merk at både med en blyant papir og med en algoritme, bør du forenkle uttrykk som star(ε)=ε
, e.ε=e
, ∅+e=e
, ∅.e=∅
hånd, bare skriv ikke kanten når det ikke er $ ∅ $, eller til og med $ ε $ for en selvsløyfe, og du ignorerer når det ikke er noen overgang mellom $ q_i $ og $ q_k $ eller $ q_j $ og $ q_k $)
Nå, hvordan bruker jeg remove(k)
? Du bør ikke fjerne de endelige eller innledende tilstandene lett, ellers vil du savne deler av språket.
for i = 1 to n: if not(final(i)) and not(initial(i)): remove(i)
Hvis du bare har en endelig tilstand $ q_f $ og en starttilstand $ q_s $, så er det endelige uttrykket:
e := star(L[s,s]) . L[s,f] . star(L[f,s] . star(L[s,s]) . L[s,f] + L[f,f])
Hvis du har flere endelige tilstander (eller til og med starttilstander), er det ingen enkel måte å slå sammen disse, bortsett fra å bruke metoden for transitiv lukking. Vanligvis er dette ikke et problem for hånd, men dette er vanskelig når du skriver algoritmen. En mye enklere løsning er å telle opp alle parene $ (s, f) $ og kjøre algoritmen på grafen (som allerede er fjernet av staten) for å få alle uttrykk $ e_ {s, f} $ antar $ s $ er den eneste opprinnelige tilstanden og $ f $ er den eneste endelige tilstanden, og deretter forenes alle $ e_ {s, f} $.
Dette, og det faktum at dette endrer språk mer dynamisk enn den første metoden gjør det mer feilutsatt når du programmerer. Jeg foreslår at du bruker en hvilken som helst annen metode.
Ulemper
Det er mange tilfeller i denne algoritmen, for eksempel for å velge hvilken node vi skal fjerne, antall endelige tilstander på slutten , det faktum at en endelig tilstand kan være initial, også osv.
Merk at nå som algoritmen er skrevet, er dette mye som metoden for transitiv lukking.Bare konteksten for bruken er annerledes. Jeg anbefaler ikke å implementere algoritmen, men å bruke metoden for å gjøre det for hånd er en god idé.
Kommentarer
- I eksemplet, 2. bilde, etter å ha fjernet noden » 2 «, det mangler en kant – sløyfekant (ab) i node A.
- @Kabamaru: Fixed. Men nå tror jeg $ \ varepsilon $ i det tredje bildet også skal være
ab
, og lignende kanskje i det endelige regulære uttrykket. - Du kan lage algoritmen jobbe for et hvilket som helst antall innledende og endelige tilstander ved å legge til en ny initial $ q ^ + $ og en ny sluttstatus $ q ^ – $, og koble disse til de opprinnelige start- og sluttstatusene med $ \ varepsilon $ -kanter. Fjern nå alle de opprinnelige tilstandene. Uttrykket blir deretter funnet ved den eneste gjenværende kanten fra $ q ^ + $ til $ q _- $. Konstruksjonen vil ikke gi løkker på $ q ^ + $ eller $ q _- $ da disse statene ikke har inngående hhv. utgående kanter. Eller hvis du er streng, vil de ha etiketter som representerer det tomme settet.
- Det er fortsatt et problem med det andre eksemplet: før forenkling aksepterer automaten » ba «, (1, 3, 1) men etter forenkling betyr det ikke ‘ t.
Svar
Metode
Den fineste metoden jeg har sett er en som uttrykker automaten som ligningssystem for (vanlige) språk som kan bli løst. Det er spesielt hyggelig da det ser ut til å gi mer kortfattede uttrykk enn andre metoder.
La $ A = (Q, \ Sigma, \ delta, q_0, F) $ en NFA uten $ \ varepsilon $ – overganger. Opprett ligningen for hver stat $ q_i $
$ \ qquad \ displaystyle Q_i = \ bigcup \ limits_ {q_i \ overset {a} {\ to} q_j} aQ_j \ cup \ begin {cases} \ {\ varepsilon \} &, \ q_i \ i F \\ \ emptyset &, \ text {else} \ end {cases} $
der $ F $ er settet med endelige tilstander og $ q_i \ overskudd {a} {\ to} q_j $ betyr at det er en overgang fra $ q_i $ til $ q_j $ merket med $ a $ . Hvis du leser $ \ cup $ som $ + $ eller $ \ mid $ (avhengig av definisjonen av vanlig uttrykk), ser du at dette er en ligning av regulære uttrykk.
For å løse systemet trenger du assosiativitet og distribusjon av $ \ cup $ og $ \ cdot $ (streng sammenkobling), kommutativitet av $ \ cup $ og Ardens Lemma ¹:
La $ L, U, V \ subseteq \ Sigma ^ * $ vanlige språk med $ \ varepsilon \ notin U $. Deretter
$ \ qquad \ displaystyle L = UL \ cup V \ quad \ Longleftrightarrow \ quad L = U ^ * V $
Løsningen er et sett med regulære uttrykk $ Q_i $, en for hver stat $ q_i $. $ Q_i $ beskriver nøyaktig de ordene som kan aksepteres av $ A $ når de startes i $ q_i $; derfor er $ Q_0 $ (hvis $ q_0 $ er den opprinnelige tilstanden) ønsket uttrykk.
Eksempel
For klarhets skyld betegner vi singletonsett etter elementet, dvs. $ a = \ {a \} $. eksempel skyldes Georg Zetzsche.
Tenk på t hans NFA:
[ kilde ]
Det tilsvarende ligningssystemet er:
$ \ qquad \ begin {align} Q_0 & = aQ_1 \ cup bQ_2 \ kopp \ varepsilon \\ Q_1 & = bQ_0 \ kopp aQ_2 \\ Q_2 & = aQ_0 \ kopp bQ_1 \ slutt {align} $
Koble nå den tredje ligningen til den andre:
$ \ qquad \ begin {align} 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} $
For det siste trinnet bruker vi Ardens Lemma med $ L = Q_1 $, $ U = ab $ og $ V = (b \ cup aa) \ cdot Q_0 $. Merk at alle de tre språkene er vanlige og $ \ varepsilon \ notin U = \ {ab \} $, slik at vi kan bruke lemmaet. Nå kobler vi dette resultatet til den første ligningen:
$ \ qquad \ begin {align} Q_0 & = a (ab) ^ * (b \ cup aa ) Q_0 \ kopp baQ_0 \ kopp bb (ab) ^ * (b \ kopp aa) Q_0 \ kopp \ varepsilon \\ & = ((a \ kopp bb) (ab) ^ * (b \ cup aa) \ cup ba) Q_0 \ cup \ varepsilon \\ & = ((a \ cup bb) (ab) ^ * (b \ cup aa) \ cup ba) ^ * \ qquad \ text {(av Ardens Lemma)} \ end {align} $
Dermed har vi funnet et vanlig uttrykk for språket som aksepteres av ovennevnte automat, nemlig
$ \ qquad \ displaystyle ((a + bb) (ab) ^ * (b + aa) + ba) ^ *. $
Merk at den er ganske kortfattet (sammenlign med resultat av andre metoder) men ikke unikt bestemt; å løse ligningssystemet med en annen sekvens av manipulasjoner fører til andre – ekvivalente! – uttrykk.
- For et bevis på Arden » s Lemma, se her .
Kommentarer
- Hva er tidskompleksiteten til denne algoritmen? Er det en begrensning på størrelsen på det produserte uttrykket?
- @jmite: Jeg aner ikke. Jeg tror ikke ‘ jeg ‘ prøver å implementere dette (andre metoder ser ut til å være mer gjennomførbare i denne forbindelse) men bruker det som en penn-og-papir-metode.
- Her ‘ sa Prolog implementering av denne algoritmen: github.com / wvxvw / intro-to-automata-theory / blob / master / automata / … men dens
maybe_union/2
predikat kan bruke mer arbeid (spesielt for å eliminere vanlig prefiks) for å gjøre ryddigere regulære uttrykk. En annen måte å se denne metoden på er å forstå den som oversettelse fra regex til høyre-lineær grammatikk, der språk med Prolog-lignende forening eller ML-lignende mønstermatching gir en veldig god transduser, så det ‘ er ikke bare en penn-og-papir-algoritme 🙂 - Bare ett spørsmål. Ε i den første ligningen er fordi Qo er en starttilstand eller fordi den ‘ er en endelig tilstand? Samme måte hvis jeg har to slutttilstander gjelder?
- @PAOK Sjekk definisjonen av $ Q_i $ over (linjen); det ‘ s fordi $ q_0 $ er en endelig tilstand.
Svar
Brzozowski algebraisk metode
Dette er den samme metoden som den som er beskrevet i Raphaels svar , men fra et punkt av visning av en systematisk algoritme, og så, faktisk algoritmen. Det viser seg å være enkelt og naturlig å implementere når du vet hvor du skal begynne. Det kan også være lettere for hånd om det å tegne alle automatene er upraktisk av en eller annen grunn. / p>
Når du skriver en algoritme, må du huske at ligningene alltid må være lineære, slik at du har en god abstrakt representasjon av ligningene, noe du kan glemme når du løser for hånd.
Ideen om algoritmen
Jeg vil ikke beskrive hvordan den fungerer siden den er godt utført i Raphaels svar som jeg foreslår å lese før. I stedet fokuserer jeg på i hvilken rekkefølge du skal løse ligningene uten å gjøre for mye ekstra co mputasjoner eller ekstra tilfeller.
Starter fra Ardens regel «sin geniale løsning $ X = A ^ * B $ til språkligningen $ X = AX∪B $ kan vi betrakte automaten som et sett med ligninger av skjemaet:
$$ X_i = B_i + A_ {i, 1} X_1 +… + A_ {i, n} X_n $$
vi kan løse dette ved induksjon på $ n $ ved å oppdatere matrisen $ A_ {i, j} $ og $ B_ {i, j} $ tilsvarende. På trinnet $ n $ har vi:
$$ X_n = B_n + A_ {n, 1} X_1 + … + A_ {n, n} X_n $$
og Ardens regel gir oss:
$$ X_n = A_ {n, n} ^ * (B_n + A_ {n, 1} X_1 + … + A_ {n, n-1} X_ {n -1}) $$
og ved å sette $ B «_n = A_ {n, n} ^ * B_n $ og $ A» _ {n, i} = A_ {n, n} ^ * A_ {n, i} $ får vi:
$$ X_n = B «_n + A» _ {n, 1} X_1 + … + A «_ {n, n-1} X_ {n -1} $$
og vi kan da fjerne alle behovene til $ X_n $ i systemet ved å sette for $ i, j < n $:
$$ B «_i = B_i + A_ {i, n} B» _n $$ $$ A «_ {i, j} = A_ {i, j} + A_ {i, n} A «_ {n, j} $$
Når vi har løst $ X_n $ når $ n = 1 $, får vi en ligning som denne:
$$ X_1 = B» _1 $$
uten $ A «_ {1, i} $. Dermed fikk vi vårt vanlige uttrykk.
Algoritmen
Takket være dette kan vi bygge algoritmen. For å ha samme konvensjon enn i induksjonen ovenfor, vil vi si at den opprinnelige tilstanden er $ q_1 $ og at antall stater er $ m $. Først initialiseringen for å fylle $ B $:
for i = 1 to m: if final(i): B[i] := ε else: B[i] := ∅
og $ 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] := ∅
og deretter løsningen:
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]
det endelige uttrykket er da:
e := B[1]
Implementering
Selv om det kan virke som et ligningssystem som virker for symbolsk for en algoritme, er dette godt egnet for en implementering. Her er en implementering av denne algoritmen i Ocaml (ødelagt lenke) . Merk at bortsett fra funksjonen brzozowski
, er alt å skrive ut eller å bruke for Raphaels eksempel. Merk at det er en overraskende effektiv funksjon for forenkling av regulære uttrykk simple_re
.
Kommentarer
- Linken er død …
- Implementering i Javascript: github.com/devongovett/regexgen/blob/master/src/regex.js
- Takk for denne flotte forklaringen. Hvis jeg forstår riktig, initialiserings-pseudokoden din antar at for gitt i og j er det høyst en slik at (i, a, j) er en overgang. Dette er riktig hvis vi er enige om å merke denne overgangen med regexp som samsvarer med alle bokstavene i Σ som merker overgang fra i til j i bokstavsautomaten, men da er notasjonen din a i bit litt rart da den egentlig ikke er en bokstav. Hvis vi går bokstav for bokstav kan vi ha flere overganger fra i til j og må gjøre foreningen av etikettene sine i løkkehuset.
Svar
Transitiv lukkemetode
Denne metoden er enkel å skrive i en form av en algoritme, men genererer absurd store regulære uttrykk og er upraktisk hvis du gjør det for hånd, mest fordi dette er for systematisk. Det er en god og enkel løsning for en algoritme.
Nøkkelideen
La $ R ^ k_ {i, j} $ representere det regulære uttrykket for strengene som går fra $ q_i $ til $ q_j $ ved å bruke statene $ \ {q_1,…, q_k \} $. La $ n $ være antall tilstander i automaten.
Anta at du allerede kjenner det vanlige uttrykket $ R_ {i, j} $ fra $ q_i $ til $ q_j $ uten mellomtilstanden $ q_k $ (unntatt ekstremiteter), for alle $ i, j $. Da kan du gjette hvordan å legge til en annen tilstand vil påvirke det nye regulære uttrykket $ R «_ {i, j} $: det endres bare hvis du har direkte overganger til $ q_k $, og det kan uttrykkes slik:
$$ R «_ {i, j} = R_ {i, j} + R_ {i, k}. R_ {k, k} ^ *. R_ {k, j} $$
($ R $ er $ R ^ {k-1} $ og $ R «$ er $ R ^ k $.)
Eksempel
Vi vil bruke samme eksempel som i Raphaels svar . Først kan du bare bruke de direkte overgangene.
Her er første trinn (merk at en selvsløyfe med etiketten $ a $ ville ha forvandlet den første $ ε $ til $ (ε + a) $.
$$ R ^ 0 = \ begin {bmatrix} ε & a & b \\ b & ε & a \\ a & b & ε \ end {bmatrix} $$
På det andre trinnet kan vi bruke $ q_0 $ (som omdøpes til $ q_1 $ for oss, fordi $ R ^ 0 $ allerede er brukt til formålet ovenfor). Vi vil se hvordan $ R ^ 1 $ fungerer.
Fra $ q_2 $ til $ 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 $.
Hvorfor er det? Å gå fra $ q_2 $ til $ q_2 $ ved å bare bruke $ q_1 $ som en mellomtilstand kan gjøres ved å bli her ($ ε $) eller gå til $ q_1 $ ($ a $), løpe der ($ ε ^ * $) og kommer tilbake ($ b $).
$$ R ^ 1 = \ begin {bmatrix} ε & a & b \\ b & ε + ba & a + bb \\ a & b + aa & ε + ab \ end {bmatrix} $$
Du kan beregne slik $ R ^ 2 $ og $ R ^ 3 $ også og $ R ^ 3_ {1,1 } $ vil gi deg det endelige uttrykket fordi $ 1 $ er både innledende og endelig. Merk at mye forenkling av uttrykk har blitt gjort her. Ellers ville den første $ a $ på $ R ^ 0 $ være $ (∅ + a) $ og den første $ a $ på $ R ^ 1 $ ville være $ ((∅ + a) + ε (ε) ^ * a ) $.
Algoritme
Initialisering:
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
Transitiv lukking:
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)
Da er det endelige uttrykket (antar at $ q_s $ er den opprinnelige tilstanden):
e := ∅ for i = 1 to n: if final(i): e := e + R[s,i,n]
Men du kan forestille deg det genererer stygge regulære uttrykk. Du kan virkelig forvente ting som $ (∅) ^ * + (a + (∅) ^ *) (ε) ^ * (a + ∅) $ som representerer samme språk som $ aa $. Merk at å forenkle et vanlig uttrykk er nyttig i praksis.
Legg igjen en kommentar