Pytania otagowane jako regular-expressions

Pytania o teorię wyrażeń regularnych, zarówno w sensie oryginalnej definicji Kleene, jak i wyrażeń regularnych POSIX.

1
Jakie algorytmy istnieją do budowy DFA, który rozpoznaje język opisany przez dane wyrażenie regularne?
Wszystkie moje podręczniki używają tego samego algorytmu do tworzenia DFA, biorąc pod uwagę regex: Najpierw utwórz NFA, który rozpoznaje język regex, a następnie, używając konstrukcji podzbioru (aka „powerset”), przekonwertuj NFA na równoważny DFA ( opcjonalnie minimalizując DFA). Kiedyś słyszałem też, jak profesor wspomina o istnieniu innych algorytmów. Czy ktoś o …
2
Taksonomia znaczących automatów wyrażeń regularnych
Próbuję opracować systematykę algorytmów do przekształcania wyrażeń regularnych w automaty, aby przeprowadzić pewne testy empiryczne ich właściwości złożoności w określonych domenach. Znam kilka „większych” nazw, np. Thompson „Algorytm wyszukiwania wyrażeń regularnych”, Thompson, 1968 Glushkov „Nowy algorytm kwadratowy do przekształcenia wyrażenia regularnego w automat”, Ponty i in. al. 1996 Antimirov „Częściowe …
1
Wyrażenia regularne bez zmian
Zastanawiałem się, jakie zestawy języków są generowane przez ograniczenia wyrażeń regularnych. Załóżmy, że wszystkie ograniczenia mają stały symbol dla każdego elementuΣΣ\Sigmai konkatenacja. Następnie można utworzyć osiem klas poprzez obecność lub brak dopełniacza / negacji, zmiany / unii i gwiazdy Kleene. (Tak, „normalne” wyrażenia regularne nie majądoC^C operator, ale tutaj jest …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.