Wyrażenia regularne a algorytm Floyda-Warshalla

Krótka notatka o fajnym połączeniu między dwoma światami

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”