Pytania o teorię wyrażeń regularnych, zarówno w sensie oryginalnej definicji Kleene, jak i wyrażeń regularnych POSIX.
Mam na myśli następujący problem: Chcę znaleźć wyrażenie regularne, które pasuje do określonego zestawu ciągów (np. Prawidłowe adresy e-mail) i nie pasuje do innych (nieprawidłowe adresy e-mail). Załóżmy, że przez wyrażenie regularne rozumiemy dobrze zdefiniowaną maszynę skończoną, nie znam...
Zapytaj nawet kogoś, kto ma doświadczenie w informatyce, co to jest wyrażenie regularne, a odpowiedź prawdopodobnie wykroczy poza ograniczenie bycia w zasięgu automatu skończonego. Na przykład „wyrażenie regularne” /^1?$|^(11+?)\1+$/ stworzona przez znaną osobowość Perla Abigail (i część...
Dobrze wiadomo, że wyrażenie regularne może zostać rozpoznane przez niedeterministyczny automat skończony o wielkości proporcjonalnej do wyrażenia regularnego lub przez deterministyczny FA, który jest potencjalnie większy wykładniczo. Ponadto, biorąc pod uwagę ciąg i wyrażenie regularne , NFA...
Zastanawiałem się, czy istnieje `` lepszy '' (wyjaśnię, w jakim sensie) algorytm rozpoczynający się od DFA i konstruujący wyrażenie regularne r takie, że L ( A ) = L ( r ) , niż ten w książka Hopcroft i Ullman (1979). Tam, zbiory R k i j są używane do reprezentowania komplety strun, które odbywają...
Dlaczego języki regularne (i te wyrażenia regularne) nazywane są „regularnymi”? Dużo prawidłowości występuje również w językach bezkontekstowych i innych rodzajach języków. Przypuszczam, że na początku zastosowano przymiotnik „zwykły” w celu odróżnienia tego rodzaju języków od innych...
Oprócz (deterministycznej) złożoności komunikacji cc(R)cc(R)cc(R) relacji RRR , inną podstawową miarą ilości potrzebnej komunikacji jest numer podziału protokołu pp(R)pp(R)pp(R) . Zależność między tymi dwoma miarami jest znana aż do stałego współczynnika. Monografia Kushilevitza i Nisana (1997)...
Powszechnie wiadomo, że następujący problem jest związany z PSPACE: Biorąc pod uwagę wyrażenie regularne , czy L ( β ) = Σ ∗ ?ββ\betaL ( β) = Σ∗L(β)=Σ∗L(\beta) = \Sigma^* Co z określeniem równoważności z innymi (stałymi) wyrażeniami regularnymi ?αα\alpha Biorąc pod uwagę wyrażenie regularne...
Większość współczesnych implementacji wyrażeń regularnych, takich jak Perl lub .NET, wykracza poza klasyczną informatyczną definicję REGEX z funkcjami takimi jak lookahead i lookbehind. Czy te funkcje umożliwiają analizowanie instrukcji, których nie można opisać za pomocą skończonego automatu bez...
Zastanawiałem się, czy specyfikacja JSON definiuje zwykły język. Wydaje się to dość proste, ale nie jestem pewien, jak sam to udowodnić. Powodem, dla którego pytam, jest to, że zastanawiałem się, czy można użyć wyrażeń regularnych, aby skutecznie przetworzyć JSON. Czy ktoś z wystarczającą liczbą...
Dwadzieścia lat temu zbudowałem pakiet wyrażeń regularnych, który obejmował konwersje wyrażeń regularnych na maszynę skończoną (DFA) i obsługiwał wiele zamkniętych operacji wyrażeń regularnych (gwiazda Kleene, konkatenacja, operacje odwrotne, ustawianie itp.). Nie byłem pewien co do najgorszej...
(Uogólniona) wysokość gwiazdy w języku jest minimalnym zagnieżdżeniem gwiazd Kleene wymaganym do przedstawienia języka za pomocą rozszerzonego wyrażenia regularnego. Przypomnijmy, że rozszerzonym wyrażeniem regularnym ponad skończonych alfabet spełnia następujące:ZAAA (1) i są rozszerzone...
Wiadomo, że minimalizowanie rozmiaru wyrażenia regularnego jest pełne dla PSPACE, nawet jeśli mamy specyfikację języka jako DFA . Jakie są wyniki, jeśli język jest skończony? Problem ten można rozważyć w dwóch modelach: Dane wejściowe to wszystkie ciągi w języku, a rozmiar wejściowy mierzymy...
Czy istnieje jakaś znana „ładna” hierarchia L0⊆L1⊆L2⊆…L0⊆L1⊆L2⊆…L_0 \subseteq L_1 \subseteq L_2 \subseteq \dots (może być skończona) w klasie zwykłych języków LLL ? Przyjemnie tutaj, klasy w każdej hierarchii przechwytują różną ekspresję / siłę / złożoność. Przynależność do każdej klasy jest...
Zainspirowany tym pytaniem ciekawi mnie: Jaka jest najgorsza złożoność sprawdzania, czy dany DFA akceptuje ten sam język jako dane wyrażenie regularne? Czy to jest znane? Można mieć nadzieję, że ten problem występuje w P - że algorytm ma wielomian wielkości
Interesuje mnie klasyczny problem REGULARNE WŁĄCZENIE JĘZYKA. Biorąc pod uwagę wyrażenie regularne , oznaczamy przez L ( E ) powiązany z nim język regularny. (Wyrażenia regularne są na stałej alfabetu Ď z unii operacji, Kleene-gwiazdkowe i konkatenacji).miEEL ( E)L(E)L(E)ΣΣ\Sigma Dane wejściowe:...
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...
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,...
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...