Omdannelse af regulært udtryk til automat

Vi viser, hvordan man omdanner et vilkårligt regulært udtryk til en ikke-deterministisk endelig automat.

Eksempel

Før vi beskriver selve algoritmen, viser vi på et eksempel, hvad det egentlig handler om. Lad os se på dette regulære udtryk: a(b|c)x^∗. Med ord kan vi beskrive det sprog, som det regulære udtryk genererer, som de ord, der begynder med bogstavet »a«, derefter følger enten bogstavet »b« eller »c«, og så følger et vilkårligt antal bogstaver »x«. Kan vi konstruere en automat, der accepterer dette sprog? Det kan vi da godt, se her:

Denne automat accepterer tydeligvis det samme sprog. Det er derfor oplagt at spørge, om der for hvert regulært udtryk findes en automat, som accepterer det pågældende sprog. Ja, det gør der.

Beskrivelse af algoritmen til omdannelse af regulært udtryk til automat

Vi antager, at input er et regulært udtryk R. Fra den foregående del om regulære udtryk ved vi, at et regulært udtryk kan have i alt seks forskellige former. Vi skelner derfor mellem seks tilfælde:

1. R = a for et symbol a ∈ Σ. Det regulære udtryk er altså blot ét symbol fra alfabetet Σ, som vi arbejder over. En automat, der accepterer ét symbol a, ville se således ud:

   

2. R = ϵ, det tomme ord. En automat, der accepterer det tomme ord, ville se således ud:

   

3. R = ∅, et regulært udtryk, der genererer det tomme sprog. En automat, der genkender et sådant sprog, er denne:

   

4. R = R₁ ∪ R₂, hvor R₁, R₂ er regulære udtryk. Vi ved allerede, at foreningen af regulære sprog igen er et regulært sprog, og at vi kan konstruere en automat, der accepterer et sådant sprog. Med andre ord antager vi, at vi har automater, som genkender de sprog, der genereres af udtrykkene R₁ og R₂, og ud fra dem konstruerer vi en automat, der accepterer det sprog, som udtrykket R₁ ∪ R₂ genererer. Eksempel: hvis R₁ = a og R₂ = ϵ, får vi efter fremgangsmåden denne automat:

   

5. R = R₁ ∘ R₂, hvor R₁, R₂ er regulære udtryk. Det er det samme tilfælde som i det forrige punkt. Konkatenering af regulære sprog giver et regulært sprog, og vi kan derfor konstruere en automat, der accepterer et sådant sprog. Så hvis R₁ = a, R₂ = b, ville konkateneringen se således ud:

   

6. $R=(R_1^{\ast })$, hvor R₁ er et regulært udtryk. Vi ved igen, at Kleene-stjernen af et regulært sprog er et regulært sprog. Så hvis R = a^∗, ville automaten se således ud:

   

Ved gradvis at anvende disse punkter omdanner vi hele det regulære udtryk til en endelig automat.

Samlet eksempel

Vi prøver at omdanne det regulære udtryk (a|bc)^∗. Trin for trin får vi disse automater:

Denne resulterende automat accepterer det sprog, som det regulære udtryk (a|bc)^∗ genererer. Automaten er selvfølgelig vildt kompliceret, og der findes helt sikkert en meget enklere automat, som accepterer det samme sprog. Vi kan bruge algoritmen til omdannelse af NFA til DFA og derefter foretage en minimering af automaten.

Kilder

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