2022 AFJ Cvičenie č. 4 - Regulárne výrazy, ich konverzia na NKA

Zhrnutie prednášky

Cvičenie ukazuje praktické použitie Thompsonovej konštrukcie na prevod regulárneho výrazu (01 ∪ 10)*(ε ∪ 0 ∪ 1) na nedeterministický konečný automat s epsilon prechodmi. Výraz sa najprv rozloží na strom podvýrazov pomocou zjednotenia, zreťazenia a iterácie, až po elementárne výrazy (ε, symbol 0, symbol 1). Automat sa potom skladá zdola nahor: najprv automaty pre 0 a 1, ich zreťazením automaty pre 01 a 10, následne zjednotením automat pre 01 ∪ 10 a potom iteráciou automat pre (01 ∪ 10)*. Pri zreťazení sa akceptačné stavy prvého automatu spoja epsilon prechodmi s počiatočným stavom druhého a prestanú byť akceptačné. Pri zjednotení sa pridá nový počiatočný stav s epsilon prechodmi do pôvodných počiatočných stavov. Pri iterácii sa pridá nový počiatočný akceptačný stav s epsilon prechodom do pôvodného počiatočného stavu a epsilon prechody z akceptačných stavov späť.

• - Thompsonova konštrukcia prevádza každý regulárny výraz na ekvivalentný konečný automat.
• - Výraz sa rozkladá na strom podvýrazov, ktorého listy sú elementárne výrazy (∅, ε, symbol).
• - Automat sa buduje zdola nahor z menších automatov pomocou troch konštrukcií.
• - Zreťazenie: epsilon prechody z akceptačných stavov prvého automatu do počiatočného stavu druhého, pôvodné akceptačné stavy prvého sa zrušia.
• - Zjednotenie: nový počiatočný stav s epsilon prechodmi do počiatočných stavov oboch automatov.
• - Iterácia: nový počiatočný akceptačný stav s epsilon prechodom do pôvodného počiatočného stavu a epsilon prechody z akceptačných stavov späť.
• - Výraz (01 ∪ 10)*(ε ∪ 0 ∪ 1) popisuje reťazce zložené z opakovaných dvojíc 01 alebo 10 s voliteľnou príponou ε, 0 alebo 1.

Zhrnutie pripravené s pomocou AI z prepisu videa.