Pytania otagowane jako regular-expressions

Pytania o wyrażenia regularne, formalizm opisu języków regularnych.

4
Jak przekonwertować skończone automaty na wyrażenia regularne?
Konwersja wyrażeń regularnych na (minimalne) NFA, które akceptują ten sam język, jest łatwa dzięki standardowym algorytmom, np . Algorytmowi Thompsona . Drugi kierunek wydaje się jednak bardziej nużący, a czasem wynikowe wyrażenia są nieuporządkowane. Jakie są algorytmy przekształcania NFA w równoważne wyrażenia regularne? Czy są zalety dotyczące złożoności czasu lub …
1
Czy regex golf NP-Complete?
Jak widać na ostatnim pasku XKCD i najnowszym poście na bloguwedług Petera Norviga (i opowiadania Slashdota z tym ostatnim) „regex golf” (który można by lepiej nazwać problemem separacji wyrażeń regularnych) jest zagadką polegającą na zdefiniowaniu najkrótszego możliwego wyrażenia regularnego, które akceptuje każde słowo w zestawie A i nie ma słowa …
4
Jak symulować odwołania wsteczne, wyprzedzenia i spojrzenia w automatach skończonych?
To pytanie zostało przeniesione z Przepełnienia stosu, ponieważ można na nie odpowiedzieć na Computer Science Stack Exchange. Migrował 7 lat temu . Stworzyłem prosty leksymetr i analizator wyrażeń regularnych, aby pobrać wyrażenie regularne i wygenerować jego drzewo analizy. Utworzenie niedeterministycznego automatu skończonego z tego drzewa analizy jest stosunkowo proste w …
6
Jaki jest związek między językami programowania, wyrażeniami regularnymi i językami formalnymi
Rozejrzałem się w sieci, szukając odpowiedzi na to pytanie i wydaje się, że wszyscy domyślnie znają odpowiedź oprócz mnie. Przypuszczalnie dzieje się tak, ponieważ jedynymi osobami, które się opiekują, są osoby z wyższym wykształceniem na ten temat. Z drugiej strony zostałem wrzucony w głęboki koniec za zadanie do szkoły średniej. …
1
Wyrażenia regularne z odniesieniami wstecznymi do jednoznacznego alfabetu
Oprawa: wyrażenia regularne z referencjami wstecznymi język jednoargumentowy (alfabet 1-symbolowy) Czy w tym ustawieniu można rozstrzygać następujący problem: Biorąc pod uwagę wyrażenie regularne z odniesieniami wstecznymi, czy definiuje ono zwykły język? Na przykład (aa+)\1definiuje zwykły język, podczas gdy (aa+)\1+nie. Czy możemy zdecydować, który jest właściwy? Dla konkretności, „wyrażenia regularne z …
2
Czy dla każdego wyrażenia „zła” istnieje nie-zła alternatywa, czy też diabeł w gramatyce?
Najwyraźniej ataki ReDos wykorzystują właściwości niektórych (poza tym użytecznych) wyrażeń regularnych ... zasadniczo powodując eksplozję możliwych ścieżek przez wykres zdefiniowany przez NFA. Czy można uniknąć takich problemów, pisząc równoważne wyrażenie „non-evil”? Jeśli nie (w związku z tym gramatyka nie może być obsługiwana przez NFA w praktycznej czasoprzestrzeni), jakie metody analizy …
3
Dlaczego operator gwiazdy Kleene jest również nazywany operatorem „zamykania” Kleene?
Przekonałem się, że jeśli nie rozumiem etymologii kryjącej się za terminem cs / programowanie, zwykle oznacza to, że przeoczyłem lub źle zrozumiałem jakąś ważną koncepcję. Nie rozumiem, dlaczego gwiazda Kleene jest również nazywana zamknięciem Kleene. Czy ma to związek z zamknięciami w programowaniu, funkcją ze związanymi zmiennymi nielokalnymi? ... po …
2
Czy krzyżówki wyrażeń regularnych są trudne NP?
Pewnego dnia wygłupiałem się na tej stronie: http://regexcrossword.com/ i zastanawiałem się, jaki był najlepszy sposób rozwiązania tego problemu. Czy potrafisz rozwiązać następujący problem w czasie wielomianowym, czy jest to trudne NP? Biorąc pod uwagę siatkę NxM z N wyrażeniami regularnymi dla kolumn i M dla wierszy, znajdź dowolne rozwiązanie siatki, …
1
Czy POSIX BRE może wyrażać wszystkie zwykłe języki?
Wygląda na to, że „podstawowe wyrażenia regularne” zdefiniowane w POSIX.1-2008 nie obsługują naprzemiennego działania a|b(chociaż niektóre implementacje grep rozpoznają wersję ucieczkową \|). Skoro zwykłe języki są z definicji zamknięte w unii, czy to oznacza, że ​​POSIX BRE ma mniejszą moc ekspresji niż automat skończony? Czy jest jakiś sposób na symulację …
4
Dlaczego w Regexach nie ma permutacji? (Nawet jeśli wydaje się, że zwykłe języki to potrafią)
Problem Nie ma łatwego sposobu na uzyskanie permutacji za pomocą wyrażenia regularnego. Permutacja: Uzyskanie słowa („aabc”) w innym porządku, bez zmiany liczby lub rodzaju liter.w=x1…xnw=x1…xnw=x_1…x_n Regex: wyrażenie regularne. Dla weryfikacji: „Permutacje regexów bez powtórzeń” Odpowiedź tworzy kod JavaScript zamiast wyrażenia regularnego, zakładając, że byłoby to prostsze. „Jak znaleźć wszystkie permutacje …
3
Zwykłe języki, których nie można wyrazić za pomocą tylko 2 operacji wyrażenia regularnego
Myślałem, że wszystkie języki regularne można wyrazić za pomocą wyrażeń regularnych (jeśli język jest regularny, można go wyrazić za pomocą wyrażenia regularnego), ale powiedziano mi, że potrzebujesz do tego wszystkich trzech operacji regularnych (konkatenacji, zjednoczenia i gwiazdki) trzymać. Powiedziano mi na przykład, że jeśli mogę korzystać tylko z operacji wyrażenia …
1
Różnica między wyrażeniem regularnym a gramatyką w automatach
Jestem nowy w automatach. Krótkie wprowadzenie do wyrażeń regularnych otrzymałem wczoraj. Przeczytałem różne reguły definiujące wyrażenie regularne. Ale nie jestem w stanie odróżnić wyrażeń regularnych od gramatyki języka (nie uczono mnie gramatyki wyrażeń regularnych). Rozumiem, że gramatyka pomaga nam generować poprawne ciągi w języku, ale wtedy właśnie takie są reguły …
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.