Omvandling av reguljärt uttryck till automat

Vi ska se hur man omvandlar vilket som helst reguljärt uttryck till en icke-deterministisk ändlig automat.

Exempel

Innan vi beskriver själva algoritmen tar vi ett exempel, så att du ser vad det handlar om. Vi har det här reguljära uttrycket: a(b|c)x^∗. Med ord beskriver vi språket som uttrycket genererar så här: orden börjar med bokstaven ”a”, därefter kommer antingen ”b” eller ”c”, och sedan kommer hur många ”x” som helst. Kan vi konstruera en automat som accepterar det här språket? Javisst, titta:

Den här automaten accepterar uppenbarligen samma språk. Då ligger frågan nära till hands om det för varje reguljärt uttryck finns en automat som accepterar språket. Det gör det.

Algoritmen för omvandling av ett reguljärt uttryck till en automat

Vi utgår från ett reguljärt uttryck R. Från den förra delen om reguljära uttryck vet vi att ett reguljärt uttryck kan ha sex olika former. Vi delar därför upp det i sex fall:

1. R = a för någon symbol a ∈ Σ. Det reguljära uttrycket är alltså bara en enda symbol ur alfabetet Σ som vi arbetar över. En automat som accepterar en enda symbol a ser ut så här:

   

2. R = ϵ, det tomma ordet. En automat som accepterar det tomma ordet ser ut så här:

   

3. R = ∅, ett reguljärt uttryck som genererar det tomma språket. En automat som känner igen ett sådant språk är den här:

   

4. R = R₁ ∪ R₂, där R₁, R₂ är reguljära uttryck. Vi vet redan att unionen av reguljära språk är ett reguljärt språk igen och att vi kan bygga en automat som accepterar ett sådant språk. Med andra ord antar vi att vi har automater som känner igen språken som uttrycken R₁ och R₂ genererar, och med hjälp av dem bygger vi en automat som accepterar språket som uttrycket R₁ ∪ R₂ genererar. Exempel: om R₁ = a och R₂ = ϵ får vi enligt metoden den här automaten:

   

5. R = R₁ ∘ R₂, där R₁, R₂ är reguljära uttryck. Samma fall som i föregående punkt. Konkatenering av reguljära språk ger ett reguljärt språk, så vi kan bygga en automat som accepterar det. Om R₁ = a och R₂ = b ser konkateneringen ut så här:

   

6. $R=(R_1^{\ast })$, där R₁ är ett reguljärt uttryck. Återigen vet vi att Kleenes stjärna av ett reguljärt språk är ett reguljärt språk. Om R = a^∗ ser automaten alltså ut så här:

   

Genom att tillämpa de här punkterna efter varandra omvandlar vi hela det reguljära uttrycket till en ändlig automat.

Ett fullständigt exempel

Vi försöker omvandla det reguljära uttrycket (a|bc)^∗. Steg för steg får vi de här automaterna:

Den slutliga automaten accepterar språket som det reguljära uttrycket (a|bc)^∗ genererar. Automaten är förstås vansinnigt komplicerad, och det finns säkert en mycket enklare automat som accepterar samma språk. Vi kan använda algoritmen för omvandling av NFA till DFA och sedan göra en minimering av automaten.

Källor

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools