Omzetting van een reguliere expressie naar een automaat

We laten zien hoe je een willekeurige reguliere expressie omzet naar een niet-deterministische eindige automaat.

Voorbeeld

Voordat we het algoritme zelf beschrijven, laten we aan een voorbeeld zien waar het ons eigenlijk om gaat. Neem deze reguliere expressie: a(b|c)x^∗. In woorden zouden we de taal die de reguliere expressie genereert zo beschrijven: woorden die beginnen met de letter “a”, gevolgd door ofwel de letter “b” ofwel “c”, en dan een willekeurig aantal letters “x”. Kunnen we een automaat construeren die deze taal accepteert? Jazeker, kijk maar:

Deze automaat accepteert duidelijk dezelfde taal. De vraag dient zich dan aan of er voor elke reguliere expressie een automaat bestaat die de gegeven taal accepteert. Nou, ja.

Beschrijving van het algoritme voor het omzetten van een reguliere expressie naar een automaat

We nemen aan dat de invoer een reguliere expressie R is. Uit het vorige deel over reguliere expressies weten we dat een reguliere expressie in totaal zes verschillende vormen kan hebben. We onderscheiden dus zes gevallen:

1. R = a voor een symbool a ∈ Σ. De reguliere expressie is dus slechts één symbool uit het alfabet Σ waarover we werken. Een automaat die één symbool a accepteert, zou er zo uitzien:

   

2. R = ϵ, het lege woord. Een automaat die het lege woord accepteert, zou er zo uitzien:

   

3. R = ∅, een reguliere expressie die de lege taal genereert. Een automaat die zo'n taal herkent, is deze:

   

4. R = R₁ ∪ R₂, waarbij R₁, R₂ reguliere expressies zijn. We weten al dat de vereniging van reguliere talen weer een reguliere taal is en dat we een automaat kunnen construeren die zo'n taal accepteert. Met andere woorden: we nemen aan dat we automaten hebben die de talen herkennen die door de expressies R₁ en R₂ worden gegenereerd, en daarmee construeren we een automaat die de taal accepteert die door de expressie R₁ ∪ R₂ wordt gegenereerd. Voorbeeld: als R₁ = a en R₂ = ϵ, dan krijgen we volgens de werkwijze deze automaat:

   

5. R = R₁ ∘ R₂, waarbij R₁, R₂ reguliere expressies zijn. Hetzelfde geval als in het vorige punt. De concatenatie van reguliere talen is een reguliere taal en we kunnen dus een automaat construeren die zo'n taal accepteert. Als R₁ = a, R₂ = b, dan zou de concatenatie er zo uitzien:

   

6. $R=(R_1^{\ast })$, waarbij R₁ een reguliere expressie is. Ook hier weten we dat de afsluiting van een reguliere taal een reguliere taal is. Als R = a^∗, dan zou de automaat er zo uitzien:

   

Door deze punten stap voor stap toe te passen, zetten we de hele reguliere expressie om in een eindige automaat.

Een compleet voorbeeld

We proberen de reguliere expressie (a|bc)^∗ om te zetten. Stap voor stap krijgen we deze automaten:

Deze resulterende automaat accepteert de taal die door de reguliere expressie (a|bc)^∗ wordt gegenereerd. Natuurlijk is de automaat waanzinnig ingewikkeld en bestaat er zeker een veel eenvoudiger automaat die dezelfde taal accepteert. We kunnen het algoritme voor het omzetten van NFA naar DFA gebruiken en daarna de automaat minimaliseren.

Bronnen

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