Na jednych z pierwszych zajęć JFiZO został przedstawiony konstruktywny dowód na równoważność siły wyrażeń regularnych oraz deterministycznych automatów skończonych (DFA). Pokazanie, że dla każdego regexa istnieje równoważny DFA jest proste, sprawa komplikuje się w drugą stronę. Tak mi się przynajmniej na początku wydawało, ale im dłużej o tym myślałem, tym bardziej odczuwałem wrażenie, że gdzieś już ten dowód widziałem.
Tutaj można sobie zobaczyć moje notatki z JFiZO i nie tylko.
Continue reading “Wyrażenia regularne a algorytm Floyda-Warshalla”