Kiedy wyrażenie regularne nie jest wyrażeniem regularnym?

Ponieważ studiuję na kursie języka formalnego, natknąłem się na te fascynujące posty ( One Two ), które opisują, jak znaleźć liczbę pierwszą za pomocą wyrażenia regularnego . Jak już powiedziałem, regexp , a nie wyrażenie regularne . Ponieważ wyrażenie regularne może pasować do ciągów obliczanych przez automat skończony i znalezienie liczby pierwszej nie może być wykonane przez FSA, wyrażenie regularne pokazane w poście na blogu nie jest do końca wyrażeniem regularnym, ponieważ wykonuje cofanie w celu dopasowania łańcucha.

Ponieważ tak naprawdę nigdy nie użyłem żadnego wyrażenia regularnego, teraz moje pytanie:

Jak mogę natychmiast rozpoznać wyrażenie regularne na podstawie „prawdziwego” wyrażenia regularnego, patrząc na nie?

Definicje: Przez wyrażenie regularne odnoszę się do pojęcia zdefiniowanego w językach formalnych. Przez wyrażenie regularne rozumiem pojęcie wspierane przez nowoczesne języki programowania; Składnia wyrażenia regularnego często zawiera dodatkowe funkcje, takie jak odwołania wsteczne. Regeksy widoczne w językach programowania są znacznie potężniejsze niż wyrażenia regularne w językach formalnych.

tl; dr backrefs.

Gdy tylko w \1wyrażeniu regularnym pojawi się (lub dowolna liczba, która nie jest używana do ucieczki przed Unicode), nie jest to wyrażenie regularne.

Backrefs pozwala dopasować, (a+)b\1które dopasowania n razy, apo których następuje b, a następnie n razy adla dowolnego n> 1. To nie jest zwykły język (jest to potomek nieregularnego języka).

Jest konieczne i prawie wystarczające, aby odnośnik zwrotny odwoływał się do grupy zawierającej wyrażenie regularne pasujące do dowolnie długiego łańcucha lub zawierającej znak *lub +. Jedyny wyjątek (który znalazłem) wyrażenia regularnego formy, w (A)B\1której A jest językiem skończonym (można go zastąpić wyliczeniem wszystkich słów, które je akceptują). Możesz przekonwertować go na word1+Bword1|word2+Bword2itp., Ponieważ A jest skończone.

Grupy rozglądające się nie usuwają regularności wyrażenia regularnego. A(?=B)Cjest przekrojem regexes AB.*i ACa przekrój 2 języków regularnych jest regularny. Negatywne spojrzenie wstecz jest podobne, z wyjątkiem użycia uzupełnienia B.*(uzupełnienia regularnych języków będących regularnymi). Lookbehind jest dokładnie taki sam, jak również A(?<=B)Cprzekrój ACi .*BC.