Prednaska + Cvicenie - Prekladace 1.3.2022 8:00

Zhrnutie prednášky

Prednáška uzatvára tému konečných automatov: nedeterministický automat možno vždy previesť na deterministický, ktorý je síce zložitejší, no pri čítaní vstupu nevyžaduje voľbu medzi vetvami. Ukázala sa pseudopascalovská funkcia simulujúca deterministický automat pomocou tabuľky prechodov a množiny koncových stavov. Slovo je rozpoznané, ak automat po načítaní celého vstupu skončí v koncovom stave. Na praktickom príklade sa overilo prijatie a zamietnutie slov a ukázal sa nástroj na automatickú konverziu. Algoritmus konštrukcie sa prebe­rie na budúcej prednáške. Cvičenie zopakovalo regulárne výrazy pre identifikátory a jedno- aj viacriadkové komentáre.

• - Ku každému nedeterministickému konečnému automatu existuje ekvivalentný deterministický automat.
• - Deterministický automat nemá pri rovnakom stave a znaku na výber a nemá ε-prechody.
• - Simulácia automatu: cyklus číta znaky vstupu a podľa tabuľky prechodov mení stav.
• - Slovo je rozpoznané, ak automat po načítaní vstupu skončí v koncovej množine stavov.
• - Algoritmus prevodu nedeterministického automatu na deterministický sa preberie na ďalšej prednáške.
• - Domáca úloha: program prevádzajúci slovne zapísané číslo na číselný tvar (opak úlohy z prvej hodiny).
• - Regulárny výraz pre identifikátor: začína písmenom alebo podčiarkovníkom, nasleduje ľubovoľný počet písmen, číslic a podčiarkovníkov.
• - Jednoriadkový komentár začína „//“, viacriadkový je ohraničený „/*“ a „*/“.

Zhrnutie pripravené s pomocou AI z prepisu videa.