Czy współczesne dialekty regularne nie są regularne?

Question

Widziałem tu kilka komentarzy, które mówią, że nowoczesne wyrażenia regularne wykraczają poza to, co można przedstawić w zwykłym języku. Jak to się dzieje?

Jakie funkcje nowoczesnych wyrażeń regularnych nie są regularne? Przykłady byłyby pomocne.

Answer 1

Pierwszą rzeczą, która przychodzi do głowy jest wsteczne:

(\w*)\s\1 

(dopasowuje grupę znaków słownych, a następnie znak spacji, a następnie ta sama grupa wcześniej dopasowane) np: hello hello mecze, hello world robi” t.

Ta konstrukcja nie jest regularna (tj .: nie może być wygenerowana przez regular grammar).

---

Inną cechą poparte Perl kompatybilne RegExp (PCRE), które nie są regularne są rekurencyjne wzorów:

\((a*|(?R))*\) 

ten może być stosowany w celu dopasowania kombinację symetrycznych nawiasach i „a” S (z wikipedia)

Answer 2

Deterministyczny lub niedeterministyczny automat skończony rozpoznaje tylko zwykłe języki, które są opisane za pomocą wyrażeń regularnych. Definicja wyrażenia regularnego jest prosta. Niech to jest alfabet. Następnie pusty zbiór, pusty ciąg i każdy element S są wyrażeniami regularnymi (ponad S). Niech wyrażenia regularne będą wyrażeniami regularnymi. Następnie związek (u | v), konkatenacji (uv) i zamknięcie (u *) z u i v są wyrażenia regularne ponad S. Ta definicja jest łatwo rozszerzona na zwykłe języki. Żadne inne wyrażenie nie jest wyrażeniem regularnym. Jak wskazano, niektóre referencje zwrotne są przykładem. Strony Wikipedii dotyczące zwykłych języków i wyrażeń są dobrymi referencjami.

W gruncie rzeczy niektóre "wyrażenia regularne" nie są regularne, ponieważ nie można skonstruować żadnego automatu określonego typu, aby je rozpoznać. Na przykład, w języku

{A^i B^I: i < = 0}

nie jest prawidłowe. Dzieje się tak dlatego, że automat akceptujący wymagałby nieskończenie wielu stanów, ale automat akceptujący zwykłe języki musi mieć skończoną liczbę stanów.

Answer 3

Kilka przykładów:

• Wyrażenia regularne wsparcie grupowania. Na przykład. w Ruby: /my (group)/.match("my group")[1] wyświetli "grupę". przechowywanie czegoś w grupie wymaga zewnętrznej pamięci, której skończony automat nie ma.
• Wiele języków, np. C#, obsługuje przechwytywanie, tzn. Że każdy mecz będzie przechwytywany na stosie - na przykład wzorzec (?<MYGROUP>.)* może wykonać wiele przechwyceń "." w tej samej grupie.
• Grupowanie używane jest do odsyłania wstecznego, co zostało wskazane powyżej przez użytkownika NullUserException. Wycofanie wsteczne wymaga jednego lub więcej zewnętrznych stosów z automatem push-down (musisz być w stanie wcisnąć coś na stos, a potem zajrzeć do niego lub pop.
• Niektóre silniki mają możliwość samodzielnego popychania i otwierania zewnętrznych Stosy i sprawdzanie, czy stos jest pusty W .NET faktycznie (?<MYGROUP>test) popycha stos, podczas gdy (?<-MYGROUP>) wyrzuca stos,
• Niektóre silniki, takie jak silnik .NET, mają zrównoważoną koncepcję grupowania - w której zewnętrzny stos może być zarówno popchnięty, jak i Zrównoważona składnia grupowania to (?<FIRSTGROUP-LASTGROUP>), która wyskakuje z LASTGROUP i odkłada przechwytywanie od czasu indeksu LASTGROUP na stosie FIRSTGROUP. Może to faktycznie być użyte do dopasowania konstrukcji nieskończenie zagnieżdżonych, która jest zdecydowanie poza możliwościami skończonego automatu n.

Prawdopodobnie istnieją inne dobre przykłady :-) Jeśli interesują Cię szczegóły implementacji zewnętrznych stosów w połączeniu z Regexem i zrównoważonym grupowaniem, a więc automaty wyższego rzędu niż skończone automaty, napisałem kiedyś dwa krótkie artykuły na ten temat (http://www.codeproject.com/KB/recipes/Nested_RegEx_explained.aspx i http://www.codeproject.com/KB/recipes/RegEx_Balanced_Grouping.aspx).

Zresztą - finitieness czy nie - ja blieve że moc, że ta dodatkowa rzeczy sprowadza się do regularnych języków jest super :-)

Br. Morten