Hur konverterar jag ändliga automatar till reguljära uttryck?
On februari 16, 2021 by adminOmvandling av reguljära uttryck till (minimal) NFA som accepterar samma språk är enkelt med standardalgoritmer, t.ex. Thompsons algoritm . Den andra riktningen verkar dock vara tråkigare och ibland är de resulterande uttrycken röriga.
Vilka algoritmer är där för att konvertera NFA till motsvarande reguljära uttryck? Finns det fördelar med avseende på tidskomplexitet eller resultatstorlek?
Detta är tänkt att vara en referensfråga. Inkludera en allmän beskrivning av din metod samt en icke-trivialt exempel.
Kommentarer
- Notera en liknande fråga över kl. cstheory.SE vilket antagligen inte passar vår publik.
- alla svar använder formell teknik för att skriva RE från DFA. Jag tror att min teknik genom analys är relativt enkel och objektiv visar jag i mitt svar : Vad är språket för denna deterministiska slutliga automat? Jag tycker att det skulle vara till hjälp någon gång. Ja, självklart någon gång använder jag själv formell metod (Arden-teorem) att skriva RE är frågan är komplex som i detta exempel: Hur man skriver ett reguljärt uttryck för en DFA
Svar
Det finns flera metoder för att göra omvandlingen från ändliga automata till reguljära uttryck. Här kommer jag att beskriva den som vanligtvis undervisas i skolan som är väldigt visuell. Jag tror att det är det mest använda i praktiken. Att skriva algoritmen är dock inte så bra.
Metod för borttagning av tillstånd
Denna algoritm handlar om att hantera grafen för automaten och är därför inte särskilt lämplig för algoritmer eftersom den behöver primitiver som … tillståndsavlägsnande. Jag kommer att beskriva den med primitiv på högre nivå.
Nyckelidén
Idén är att överväga regelbundna uttryck i kanterna och sedan ta bort mellanstatus samtidigt som kantetiketterna är konsistenta. p>
Huvudmönstret kan ses i figurerna nedan. Den första har etiketter mellan $ p, q, r $ som är reguljära uttryck $ e, f, g, h, i $ och vi vill ta bort $ q $.
När vi väl tagit bort, komponerar vi $ e, f, g, h, i $ tillsammans (samtidigt som vi behåller de andra kanterna mellan $ p $ och $ r $ men detta visas inte om detta):
Exempel
Använd samma exempel som i Raphaels svar :
tar vi successivt bort $ q_2 $:
och sedan $ q_3 $:
då måste vi fortfarande tillämpa en stjärna på uttrycket från $ q_1 $ till $ q_1 $. I det här fallet är det slutliga tillståndet också initial så vi behöver egentligen bara lägga till en stjärna:
$$ (ab + (b + aa) (ba) ^ * (a + bb)) ^ * $$
Algoritm
L[i,j]
är regexp för språket från $ q_i $ till $ q_j $. Först tar vi bort alla 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
Nu avlägsnas tillståndet. Anta att vi vill ta bort 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]
Observera att både med en penna och med en algoritm bör du förenkla uttryck som star(ε)=ε
, e.ε=e
, ∅+e=e
, ∅.e=∅
räcker att du bara inte skriver kanten när det inte är $ ∅ $, eller till och med $ ε $ för en självslinga och du ignorerar när det inte finns någon övergång mellan $ q_i $ och $ q_k $ eller $ q_j $ och $ q_k $)
Hur använder jag remove(k)
? Du bör inte ta bort slutliga eller initiala tillstånd lätt, annars kommer du att sakna delar av språket.
for i = 1 to n: if not(final(i)) and not(initial(i)): remove(i)
Om du bara har ett slutligt tillstånd $ q_f $ och ett initialt tillstånd $ q_s $ då är det sista uttrycket:
e := star(L[s,s]) . L[s,f] . star(L[f,s] . star(L[s,s]) . L[s,f] + L[f,f])
Om du har flera slutliga tillstånd (eller till och med initialtillstånd) så finns det inget enkelt sätt att slå samman dessa, förutom att tillämpa den transitiva stängningsmetoden. Vanligtvis är detta inte ett problem för hand men det är besvärligt när man skriver algoritmen. En mycket enklare lösning är att räkna upp alla par $ (s, f) $ och köra algoritmen i (redan borttagna) graf för att få alla uttryck $ e_ {s, f} $ antar $ s $ är det enda initiala tillståndet och $ f $ är det enda slutliga tillståndet och gör sedan unionen av alla $ e_ {s, f} $.
Detta och det faktum att detta ändrar språk mer dynamiskt än den första metoden gör det mer felbenägen vid programmering. Jag föreslår att du använder någon annan metod.
Nackdelar
Det finns många fall i denna algoritm, till exempel för att välja vilken nod vi ska ta bort, antalet slutliga tillstånd i slutet , det faktum att ett slutligt tillstånd också kan vara initialt osv.
Observera att nu när algoritmen är skriven så är det mycket som metoden för transitiv stängning.Endast sammanhanget för användningen är annorlunda. Jag rekommenderar inte att implementera algoritmen, men att använda metoden för att göra det för hand är en bra idé.
Kommentarer
- I exemplet, 2: a bilden, efter borttagning av nod ” 2 ”, det saknas en kant – loop edge (ab) i nod A.
- @Kabamaru: Fixed. Men nu tycker jag att $ \ varepsilon $ i den tredje bilden också ska vara
ab
, och på liknande sätt kanske i det slutliga reguljära uttrycket. - Du kan skapa algoritmen arbeta för valfritt antal initiala och slutliga tillstånd genom att lägga till en ny initial $ q ^ + $ och ett nytt slutligt tillstånd $ q ^ – $, och ansluta dessa till de ursprungliga initiala och slutliga tillstånden med $ \ varepsilon $ -kanter. Ta nu bort alla originaltillstånden. Uttrycket hittas sedan vid den enda kvarvarande kanten från $ q ^ + $ till $ q _- $. Konstruktionen ger inte slingor på $ q ^ + $ eller $ q _- $ eftersom dessa stater inte har ingående resp. utgående kanter. Eller om du är strikt kommer de att ha etiketter som representerar den tomma uppsättningen.
- Det finns fortfarande ett problem med det andra exemplet: före förenkling accepterar automaten ” ba ”, (1, 3, 1) men efter förenkling ’ t.
Svar
Metod
Den trevligaste metoden jag har sett är en som uttrycker automaten som ekvationssystem för (vanliga) språk som kan bli löst. Det är särskilt trevligt eftersom det verkar ge mer kortfattade uttryck än andra metoder.
Låt $ A = (Q, \ Sigma, \ delta, q_0, F) $ en NFA utan $ \ varepsilon $ – övergångar. Skapa ekvationen för varje delstat $ 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} $
där $ F $ är uppsättningen slutliga tillstånd och $ q_i \ överbelastning {a} {\ till} q_j $ betyder att det finns en övergång från $ q_i $ till $ q_j $ märkt med $ a $ . Om du läser $ \ cup $ som $ + $ eller $ \ mid $ (beroende på definitionen av ditt reguljära uttryck) ser du att detta är en ekvation av reguljära uttryck.
För att lösa systemet behöver du associativitet och fördelning av $ \ cup $ och $ \ cdot $ (strängkompatering), kommutativitet av $ \ cup $ och Ardens Lemma ¹:
Låt $ L, U, V \ subseteq \ Sigma ^ * $ vanliga språk med $ \ varepsilon \ notin U $. Sedan,
$ \ qquad \ displaystyle L = UL \ cup V \ quad \ Longleftrightarrow \ quad L = U ^ * V $
Lösningen är en uppsättning reguljära uttryck $ Q_i $, en för varje stat $ q_i $. $ Q_i $ beskriver exakt de ord som kan accepteras av $ A $ när de startas i $ q_i $; därför är $ Q_0 $ (om $ q_0 $ är det ursprungliga tillståndet) önskat uttryck.
Exempel
För tydlighetens skull betecknar vi singletonsatser efter deras element, dvs $ a = \ {a \} $. exempel beror på Georg Zetzsche.
Tänk på t hans NFA:
[ källa ]
Motsvarande ekvationssystem är:
$ \ qquad \ begin {align} Q_0 & = aQ_1 \ cup bQ_2 \ cup \ varepsilon \\ Q_1 & = bQ_0 \ cup aQ_2 \\ Q_2 & = aQ_0 \ cup bQ_1 \ end {align} $
Anslut nu den tredje ekvationen till den andra:
$ \ 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} $
För det sista steget tillämpar vi Ardens Lemma med $ L = Q_1 $, $ U = ab $ och $ V = (b \ cup aa) \ cdot Q_0 $. Observera att alla tre språken är vanliga och $ \ varepsilon \ notin U = \ {ab \} $, vilket gör att vi kan tillämpa lemma. Nu kopplar vi in detta resultat i den första ekvationen:
$ \ 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} $
Således har vi hittat ett regelbundet uttryck för det språk som accepteras av ovanstående automat, nämligen
$ \ qquad \ displaystyle ((a + bb) (ab) ^ * (b + aa) + ba) ^ *. $
Observera att det är ganska kortfattat (jämför med resultat av andra metoder) men inte unikt bestämt; lösning av ekvationssystemet med en annan sekvens av manipulationer leder till andra – ekvivalenta! – uttryck.
- För ett bevis på Arden ” s Lemma, se här .
Kommentarer
- Vad är tidskomplexiteten hos denna algoritm? Finns det en gräns för det producerade uttryckets storlek?
- @jmite: Jag har ingen aning. Jag tror inte ’ att jag ’ försöker implementera detta (andra metoder verkar vara mer genomförbara i detta avseende) men använder det som en penna- och pappersmetod.
- Här ’ sa Prolog-implementering av denna algoritm: github.com / wvxvw / intro-to-automata-theory / blob / master / automata / … men dess
maybe_union/2
predikat kan använda mer arbete (särskilt för att eliminera vanligt prefix) för att göra ordentliga reguljära uttryck. Ett annat sätt att se denna metod är att förstå den som översättning från regex till höger-linjär grammatik, där språk med Prolog-liknande enande eller ML-liknande mönstermatchning ger en mycket bra givare, så det ’ är inte bara en penna-och-pappersalgoritm 🙂 - Bara en fråga. Ε i den första ekvationen beror på att Qo är ett starttillstånd eller för att det ’ är ett slutligt tillstånd? Samma sätt om jag har två slutliga tillstånd gäller?
- @PAOK Kontrollera definitionen av $ Q_i $ ovan (raden); det ’ s eftersom $ q_0 $ är ett slutligt tillstånd.
Svar
Brzozowski algebraisk metod
Detta är samma metod som den som beskrivs i Raphaels svar , men från en punkt av syn på en systematisk algoritm och sedan faktiskt algoritmen. Det visar sig vara enkelt och naturligt att implementera när du vet var du ska börja. Det kan också vara lättare för hand om det inte är praktiskt att rita alla automaterna av någon anledning. / p>
När du skriver en algoritm måste du komma ihåg att ekvationerna alltid måste vara linjära så att du får en bra abstrakt representation av ekvationerna, något som du kan glömma när du löser för hand.
Idén med algoritmen
Jag kommer inte att beskriva hur det fungerar eftersom det är bra gjort i Raphaels svar som jag föreslår att läsa innan. I stället fokuserar jag på i vilken ordning du ska lösa ekvationerna utan att göra för många extra co mputationer eller extra fall.
Från Ardens regel : s geniala lösning $ X = A ^ * B $ till språkekvationen $ X = AX∪B $ kan vi betrakta automaten som en uppsättning ekvationer av formen:
$$ X_i = B_i + A_ {i, 1} X_1 + … + A_ {i, n} X_n $$
vi kan lösa detta genom induktion på $ n $ genom att uppdatera matriserna $ A_ {i, j} $ och $ B_ {i, j} $ i enlighet med detta. Vid steget $ n $ har vi:
$$ X_n = B_n + A_ {n, 1} X_1 + … + A_ {n, n} X_n $$
och Ardens regel ger oss:
$$ X_n = A_ {n, n} ^ * (B_n + A_ {n, 1} X_1 + … + A_ {n, n-1} X_ {n -1}) $$
och genom att ställa in $ B ”_n = A_ {n, n} ^ * B_n $ och $ 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} $$
och vi kan sedan ta bort alla behov av $ X_n $ i systemet genom att ställa in $ 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 ekvation så här:
$$ X_1 = B” _1 $$
utan $ A ”_ {1, i} $. Således fick vi vårt vanliga uttryck.
Algoritmen
Tack vare detta kan vi bygga algoritmen. För att ha samma konvention än i induktionen ovan kommer vi att säga att det ursprungliga tillståndet är $ q_1 $ och att antalet stater är $ m $. Först initialiseringen för att fylla $ B $:
for i = 1 to m: if final(i): B[i] := ε else: B[i] := ∅
och $ 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] := ∅
och sedan 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 sista uttrycket är då:
e := B[1]
Implementering
Även om det kan verka som ett ekvationssystem som verkar för symboliskt för en algoritm, är den här väl lämpad för en implementering. Här är en implementering av denna algoritm i Ocaml (trasig länk) . Observera att förutom funktionen brzozowski
är allt att skriva ut eller att använda för Raphaels exempel. Observera att det finns en överraskande effektiv funktion för förenkling av reguljära uttryck simple_re
.
Kommentarer
- Länken är död …
- Implementering i Javascript: github.com/devongovett/regexgen/blob/master/src/regex.js
- Tack för den här fantastiska förklaringen. Om jag förstår rätt, din initialisering pseudokod antar att för givet i och j finns det högst en sådan att (i, a, j) är en övergång. Detta är korrekt om vi går med på att märka denna övergång med regex som matchar alla bokstäver i Σ att etiketten övergår från i till j i bokstavsautomaten, men då är din notering a i bit lite konstig eftersom det inte egentligen är en bokstav. Om vi går bokstav för bokstav kan vi ha flera övergångar från i till j och måste göra föreningen av sina etiketter i loop-kroppen.
Svar
Transitiv stängningsmetod
Den här metoden är lätt att skriva i form av en algoritm, men genererar absurt stora reguljära uttryck och är opraktiskt om du gör det för hand, främst för att det här är för systematiskt. Det är dock en bra och enkel lösning för en algoritm.
Nyckelidén
Låt $ R ^ k_ {i, j} $ representera det reguljära uttrycket för strängarna som går från $ q_i $ till $ q_j $ med hjälp av staterna $ \ {q_1,…, q_k \} $. Låt $ n $ vara antalet tillstånd i automaten.
Antag att du redan känner till det reguljära uttrycket $ R_ {i, j} $ från $ q_i $ till $ q_j $ utan mellanstatus $ q_k $ (utom extremiteter), för alla $ i, j $. Då kan du gissa hur att lägga till ett annat tillstånd kommer att påverka det nya reguljära uttrycket $ R ”_ {i, j} $: det ändras bara om du har direktövergångar till $ q_k $, och det kan uttryckas så:
$$ R ”_ {i, j} = R_ {i, j} + R_ {i, k}. R_ {k, k} ^ *. R_ {k, j} $$
($ R $ är $ R ^ {k-1} $ och $ R ”$ är $ R ^ k $.)
Exempel
Vi använder samma exempel som i Raphaels svar . Först kan du bara använda de direkta övergångarna.
Här är det första steget (notera att en självslinga med etiketten $ a $ skulle ha förvandlat den första $ ε $ till $ (ε + a) $.
$$ R ^ 0 = \ begin {bmatrix} ε & a & b \\ b & ε & a \\ a & b & ε \ end {bmatrix} $$
I det andra steget kan vi använda $ q_0 $ (som bytt namn till $ q_1 $ för oss, eftersom $ R ^ 0 $ redan används för syftet ovan). Vi får se hur $ R ^ 1 $ fungerar.
Från $ q_2 $ till $ 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 $.
Varför är det? Det beror på att gå från $ q_2 $ till $ q_2 $ med endast $ q_1 $ som mellanstatus kan göras genom att stanna här ($ ε $) eller gå till $ q_1 $ ($ a $), gå där ($ ε ^ * $) och kommer tillbaka ($ b $).
$$ R ^ 1 = \ begin {bmatrix} ε & a & b \\ b & ε + ba & a + bb \\ a & b + aa & ε + ab \ end {bmatrix} $$
Du kan också beräkna $ R ^ 2 $ och $ R ^ 3 $ och $ R ^ 3_ {1,1 } $ ger dig det sista uttrycket eftersom $ 1 $ är både initialt och slutgiltigt. Observera att mycket förenkling av uttryck har gjorts här. Annars skulle den första $ a $ på $ R ^ 0 $ vara $ (∅ + a) $ och den första $ a $ på $ R ^ 1 $ skulle vara $ ((∅ + a) + ε (ε) ^ * a ) $.
Algoritm
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 stängning:
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)
Då är det sista uttrycket (antar att $ q_s $ är det ursprungliga tillståndet):
e := ∅ for i = 1 to n: if final(i): e := e + R[s,i,n]
Men du kan föreställa dig det genererar fula reguljära uttryck. Du kan verkligen förvänta dig saker som $ (∅) ^ * + (a + (∅) ^ *) (ε) ^ * (a + ∅) $ som representerar samma språk som $ aa $. Observera att det är praktiskt att förenkla ett reguljärt uttryck.
Lämna ett svar