Vztah mezi RV a KA

Metoda sousedů

  • Glushkov

  • Vezme RV a očísluje si každý jeho symbol, aby byl unikátní

  • Vytvoří množinu - začínající symboly, všechny symboly, kterými může RV začínat

  • Vytvoří množinu - dvojice symbolů takových, že v tom RV mohou sousedit (, může po něm bezprostředně následovat )

  • Vytvoří množinu - koncových symbolů, symboly kterými hodnoty RV mohou končit

  • Vznikne konečný automat nedeterministický a homogenní

../Attachments/Pasted image 20221025165710.png

Metoda derivací

  • Janusz A. Brzozowski
  • Vezmu RV a budu ho derivovat podle všech symbolů abecedy
  • Budou vznikat nové RV, každý bude stavem automatu
  • Zároveň je třeba kontrolovat, jestli ty stavy (RV) nejsou podobné, aby jich nebylo zbytečně moc
  • Koncové stavy jsou všechny RV, které obsahují
Hint

Věta: Každý regulární výraz má pouze konečný počet nepodobných derivací
Důsledek: Pro konstrukci DKA pro daný RV pomocí metody derivací stačí uvažovat pouze podobnosti () výrazů

Metoda postupné konstrukce

  • Ken Thompson
  • Sleduje definici RV
  • Sestrojí různé malé (částečné) automaty pro různé RV, které nakonec budou tvořit jeden velký automat
  • Každý malý automat (operace) vytváří 1 počáteční a 1 koncový stav

Pravidla

../Attachments/Pasted image 20221025172106.png
../Attachments/Pasted image 20221025172129.png

Příklad


../Attachments/prevod-thompson.png

Vytvořeno: 7. 8. 2024, 13:25
Poslední aktualizace: 7. 8. 2024, 13:25