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ę naprzemienności przy użyciu innych konstrukcji?

Rzeczywiście język POSIX BRE nie może wyrażać wszystkich wyrażeń regularnych, ponieważ brakuje w nim naprzemienności. Nie potrafi nawet rozpoznać wszystkich języków skończonych, nie mówiąc już o wszystkich zwykłych językach.

Na przykład nie jest rozpoznawalny jako BRE. Aby to udowodnić, zastanów się, jaką formą składniową najwyższego poziomu może być:$\{ab, ba\}$

• Nie może to być jedna z postaci jednoznakowych, ponieważ język ma słowa o długości .$\gt 1$
• To nie może być ponieważ pasowałoby to do pustego ciągu.$R^*$
• Nie może to być z wyjątkiem m = n = 1 (w takim przypadku wracamy do pierwotnego problemu), ponieważ pasowałoby to do łańcuchów o różnych długościach lub do pustego łańcucha.$R^{\{m,n\}}$$m=n=1$
• Więc to musi być konkatenacja: . Teraz zastanów się, jak rozpoznaje się b : $R_1 R_2$$ab$
  • Jeśli uznaje się b wówczas R 2 nie musi rozpoznać niczego coś innego niż pusty ciąg. Więc R 1 musi rozpoznać { a b , b a } i wróciliśmy do pierwotnego problemu.$R_1$$ab$$R_2$$R_1$$\{ab,ba\}$
  • Jeśli uznaje się , lecz nie do b wtedy R 2 musi rozpoznawać b . Ale wtedy R 1 R 2 rozpoznaje wszystkie słowa formy u b gdzie R 1 rozpoznaje u , więc R 1 nie musi niczego innego niż rozpoznać . Nie ma sposobu, aby rozpoznać b .$R_1$$a$$ab$$R_2$$b$$R_1R_2$$u b$$R_1$$u$$R_1$$a$$ba$
  • Jeśli rozpoznaje ani do b , ani się to jedynym sposobem na R rozpoznać b jest jeśli R 1 rozpoznaje pusty ciąg znaków, w którym to przypadku wracamy do pierwotnego problemu jak wyżej, ale dla R 2 to czasu.$R_1$$ab$$a$$R$$ab$$R_1$$R_2$

Kiedy „wracamy do pierwotnego problemu”, oznacza to, że jedynym rozwiązaniem do znalezienia BRE jest rozpoznanie języka to znalezienie mniejszego BRE, który ma tę samą właściwość. Jest to nieskończone zejście , więc nie ma BRE, który miałby pożądaną właściwość.

Nie sądzę, by istniała „ładna” charakterystyka języków rozpoznawalnych przez BRE, na przykład jako języków rozpoznawalnych przez „ładną” klasę automatów.

Pamiętaj, że języki rozpoznawalne przez BRE nie są tak naprawdę podklasą zwykłych języków, ponieważ odwołania wsteczne dodają mocy ekspresyjnej. Na przykład jest rozpoznawany przez BRE, ale nie jest znany jako regularny. BRE bez odwołań zwrotnych to po prostu cukier składniowy w wyrażeniach regularnych, więc języki, które mogą rozpoznać, są podklasą języków regularnych.$\{w w \mid w \in \{a,b\}^*\}$\(.*\)\1