Reguláris kifejezés átalakítása automatává

Megmutatjuk, hogyan alakíthatunk át bármely reguláris kifejezést nemdeterminisztikus véges automatává.

Példa

Mielőtt leírnánk magát az algoritmust, egy példán megmutatjuk, miről lesz szó. Adott ez a reguláris kifejezés: a(b|c)x^∗. Szavakkal azt a nyelvet, amelyet a reguláris kifejezés generál, úgy írnánk le, mint azokat a szavakat, amelyek „a” betűvel kezdődnek, utána vagy „b”, vagy „c” betű következik, majd tetszőleges számú „x” betű. Meg tudnánk szerkeszteni olyan automatát, amely ezt a nyelvet fogadja el? Hát persze, nézd:

Ez az automata nyilvánvalóan ugyanazt a nyelvet fogadja el. Adódik a kérdés, hogy minden reguláris kifejezéshez létezik-e olyan automata, amely az adott nyelvet elfogadja. Nos, igen.

A reguláris kifejezést automatává alakító algoritmus leírása

Feltesszük, hogy a bemeneten egy R reguláris kifejezés van. A reguláris kifejezésekről szóló előző részből tudjuk, hogy a reguláris kifejezésnek összesen hat különböző alakja lehet. Hat különböző esetet különböztetünk meg:

1. R = a valamilyen a ∈ Σ szimbólumra. Vagyis a reguláris kifejezés csupán egyetlen szimbóluma annak a Σ ábécének, amely felett dolgozunk. Az az automata, amely egyetlen a szimbólumot fogadna el, így nézne ki:

   

2. R = ϵ, az üres szó. Az az automata, amely az üres szót fogadná el, így nézne ki:

   

3. R = ∅, olyan reguláris kifejezés, amely az üres nyelvet generálja. Az az automata, amely ilyen nyelvet ismer fel, ez:

   

4. R = R₁ ∪ R₂, ahol R₁, R₂ reguláris kifejezések. Már tudjuk, hogy reguláris nyelvek uniója is reguláris nyelv, és hogy meg tudunk szerkeszteni olyan automatát, amely ilyen nyelvet fogad el. Más szóval feltesszük, hogy vannak automatáink, amelyek felismerik az R₁ és R₂ kifejezés által generált nyelvet, és ezek segítségével megszerkesztjük azt az automatát, amely az R₁ ∪ R₂ kifejezés által generált nyelvet fogadja el. Példa: ha R₁ = a és R₂ = ϵ, akkor az eljárás szerint ezt az automatát kapjuk:

   

5. R = R₁ ∘ R₂, ahol R₁, R₂ reguláris kifejezések. Ugyanaz az eset, mint az előző pontban. Reguláris nyelvek összefűzése reguláris nyelv, és így meg tudunk szerkeszteni olyan automatát, amely ilyen nyelvet fogad el. Tehát ha R₁ = a, R₂ = b, akkor az összefűzés így nézne ki:

   

6. $R=(R_1^{\ast })$, ahol R₁ reguláris kifejezés. Megint tudjuk, hogy reguláris nyelv lezárása reguláris nyelv. Tehát ha R = a^∗, akkor az automata így nézne ki:

   

Ezeknek a pontoknak a fokozatos alkalmazásával az egész reguláris kifejezést véges automatává alakítjuk.

Teljes példa

Megpróbáljuk átalakítani az (a|bc)^∗ reguláris kifejezést. Fokozatosan ezeket az automatákat kapjuk:

Ez a végső automata azt a nyelvet fogadja el, amelyet az (a|bc)^∗ reguláris kifejezés generál. Az automata persze rettentően bonyolult, és biztosan létezik sokkal egyszerűbb automata, amely ugyanezt a nyelvet fogadja el. Használhatjuk az NVA DVA-vá alakításának algoritmusát, majd elvégezhetjük az automata minimalizálását.

Források

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