Regulaarsest avaldisest mittedetermineeritud automaadi moodustamine

Transleermismeetodid 1997/98, Meelis Roosi individuaaltöö

Sissejuhatus - Primitiivsed automaadid - Näide 

Sissejuhatus.

Olgu meil regulaarne avaldis r. Tahame moodustada sellele regulaaravaldisele vastavat lõplikku automaati A, mis aktsepteeriks sedasama keelt, mis r.

Kasutame Thompsoni konstruktsiooni. Selle konstruktsiooni idee on seada igale regulaaravaldises esineda võivale operatsioonile vastavusse primitiivne automaat. Kogu avaldisele vastab primitiivsete automaatide lihtne kompositsioon. Korduvatele alamavaldistele seatakse vastavusse mitu vastavalt mitu primitiivset automaati, mingit optimiseerimist siin ei toimu.

Nii saadud lõplik automaat pole determineeritud, kuna me kasutame juba primitiivsetes automaatides mittedetermineeritust. Lõpliku automaadi võib hiljem muidugi eraldi determineerida.

Primitiivsed automaadid.

Igal primitiivsel automaadil on oma algolek i ja lõppolek f. Iga uue primitiivse automaadi koostamisel võtame kasutusele uue alg- ja lõppoleku. Hiljem kompositsiooni juures võivad mõned neist seisunditest osutuda üleliigseks, siis viskame nad lihtsalt minema.
  1. Tühjale sümbolile e seame vastavusse järgmise automaadi:
    Joonis 1
  2. Igale kasutatavale terminaalsele sümbolile a seame vastavusse automaadi
    Joonis 2
  3. Avaldises r esinevatele valikutele s|t seame vastavusse järgmised automaadid (kus N(s) ja N(t) on s ja t vastavad lõplikud automaadid):
    Joonis 3
  4. Avaldises r esinevatele konkatenatsioonidele st seame vastavusse järgmised automaadid:
    Joonis 4
  5. Avaldises r esinevate korduste s* seame vastavusse sellised automaadid:
    Joonis 5
  6. Alamavaldistele kujul (s) seame vastavusse sama automaadi, mis s-le, s.t. N(s).

Näide.

Võtame regulaarse avaldise a*(ba|c) ja konstrueerime sellele avaldisele vastava mitteetermineeritud lõpliku automaadi.

Kõigepealt moodustame 2. reegli järgi primitiivsed automaadid lihtsamatele osalausetele a ja c. 4. reegli abil saame a ja b jaoks konkatenatsioonile vastava automaadi. Igaühe jaoks võtame kasutusele uued olekud, mis omavahel ei kattu:

Näide, joonis 1
5. reegli abil saab esimese a arendada edasi a*-ks:
Näide, joonis 2
Nüüd ühendame ba ja c automaadid 3. reegli abil:
Näide, joonis 3
Ja lõpuks võimegi kõik vajalikud jupid 4. reegli abil kokku kombineerida. Saam järgmise automaadi:
Näide, joonis 4
See ongi üks võimalik mittedetermineeritud lõplik automaat, mis vastab meie poolt uuritud avaldisele.
Meelis Roos 25.01.1998