Pytania otagowane jako regular-expressions

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

4
Czy znalezienie minimalnego wyrażenia regularnego jest problemem NP-zupełnym?
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 dokładnej terminologii, ale uzgodnijmy pewną klasę dozwolonych wyrażeń. Zamiast ręcznie tworzyć …
6
Wyrażenia regularne nie są
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ęść zestawu testów Perla od 2002 r.) opisuje maszynę, która akceptuje tylko złożone liczby …
4
Czy istnieją „małe” maszyny, które mogą skutecznie dopasowywać wyrażenia regularne?
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 może przetestować członkostwo w czasie proporcjonalnym do | s | \ cdot | …
1
Dlaczego zwykłe języki nazywane są „zwykłymi”?
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 „nieregularnych” lub w jakiś sposób nienormalnych języków. Jeśli tak, to gdzie te inne typy …
2
Numer podziału protokołu i deterministyczna złożoność komunikacji
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) daje cc(R)/3≤log2(pp(R))≤cc(R).cc(R)/3≤log2⁡(pp(R))≤cc(R).cc(R)/3 \le \log_2(pp(R)) \le cc(R). Jeśli chodzi o drugą nierówność, łatwo jest podać …
4
Gdzie większość implementacji REGEX przypada na skalę złożoności?
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 odpychania? Jak bardzo zbliża się do ukończenia Turinga, jeśli to możliwe?
2
Czy JSON jest językiem zwykłym?
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ą przedstawicieli może dla mnie utworzyć tagi …
3
Czy niedeterministyczne skończone automaty (NDFA) można skutecznie konwertować na deterministyczne skończone automaty (DFA) w podwykładniczej przestrzeni / czasie?
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 wydajności mojego pakietu. DFA ma taką samą moc ekspresyjną jak NDFA, ponieważ NDFA w …
2
minimalizowanie wielkości wyrażeń regularnych dla zbiorów skończonych
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 sumą długości wszystkich ciągów. Dane wejściowe to …
3
Postęp w ogólnym problemie z wysokością gwiazdy?
(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 wyrażenia regularne dla wszystkich A ∈∅ , 1∅,1\emptyset, 1zaaaa ∈ Aa∈Aa\in A (2) Dla wszystkich rozszerzonych wyrażeń …
4
Hierarchie w zwykłych językach
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 „ładnie” wykazana przez niektóre elementy (w przeciwieństwie do problemu wysokości …
1
Sparametryzowana złożoność włączenia zwykłych języków
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: dwa wyrażenia regularne i E 2 Pytanie: Czy to …
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.