Omforming av regulært uttrykk til automat

Vi skal vise hvordan du omformer et vilkårlig regulært uttrykk til en ikke-deterministisk endelig automat.

Eksempel

Før vi beskriver selve algoritmen, viser vi på et eksempel hva vi egentlig skal gjøre. La oss ha dette regulære uttrykket: a(b|c)x^∗. Med ord ville vi beskrevet språket som det regulære uttrykket genererer, som ord som begynner med bokstaven «a», etterfulgt av enten bokstaven «b» eller «c» og så et vilkårlig antall bokstaver «x». Kunne vi konstruert en automat som aksepterte dette språket? Joda, se her:

Denne automaten aksepterer åpenbart det samme språket. Da melder spørsmålet seg: finnes det for hvert regulært uttrykk en automat som aksepterer språket? Jo, det gjør det.

Beskrivelse av algoritmen for å omforme et regulært uttrykk til en automat

Vi antar at vi har et regulært uttrykk R som input. Fra den forrige delen om regulære uttrykk vet vi at et regulært uttrykk kan ha til sammen seks ulike former. Vi skiller derfor mellom seks ulike tilfeller:

1. R = a for et symbol a ∈ Σ. Altså er det regulære uttrykket bare ett symbol fra alfabetet Σ vi arbeider over. En automat som skulle akseptere ett symbol a, ville sett slik ut:

   

2. R = ϵ, det tomme ordet. En automat som skulle akseptere det tomme ordet, ville sett slik ut:

   

3. R = ∅, et regulært uttrykk som genererer det tomme språket. Automaten som ville gjenkjent et slikt språk, er denne:

   

4. R = R₁ ∪ R₂, der R₁, R₂ er regulære uttrykk. Vi vet allerede at union av regulære språk igjen er et regulært språk, og at vi kan konstruere en automat som aksepterer et slikt språk. Med andre ord antar vi at vi har automater som gjenkjenner språket generert av uttrykkene R₁ og R₂, og ved hjelp av dem konstruerer vi en automat som aksepterer språket generert av uttrykket R₁ ∪ R₂. Eksempel: hvis R₁ = a og R₂ = ϵ, får vi etter framgangsmåten denne automaten:

   

5. R = R₁ ∘ R₂, der R₁, R₂ er regulære uttrykk. Samme tilfelle som i forrige punkt. Konkatenering av regulære språk er et regulært språk, og vi kan derfor konstruere en automat som skal akseptere et slikt språk. Så hvis R₁ = a, R₂ = b, ville konkateneringen sett slik ut:

   

6. $R=(R_1^{\ast })$, der R₁ er et regulært uttrykk. Vi vet igjen at Kleene-stjernen til et regulært språk er et regulært språk. Så hvis R = a^∗, ville automaten sett slik ut:

   

Ved å bruke disse punktene etter tur omformer vi hele det regulære uttrykket til en endelig automat.

Et helhetlig eksempel

Vi prøver å omforme det regulære uttrykket (a|bc)^∗. Etter hvert får vi disse automatene:

Denne resulterende automaten aksepterer språket som det regulære uttrykket (a|bc)^∗ genererer. Automaten er selvfølgelig vanvittig komplisert, og det finnes helt sikkert en mye enklere automat som aksepterer det samme språket. Vi kan bruke algoritmen for omforming av NFA til DFA og deretter utføre minimering av automaten.

Kilder

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