O POSIX BRE pode expressar todos os idiomas comuns?

Parece que "Expressões regulares básicas", conforme definidas no POSIX.1-2008 , não suportam alternância a|b(embora algumas implementações grep reconheçam a versão de escape \|).

Como as linguagens regulares são fechadas sob união por definição, isso significa que o POSIX BRE possui um poder menos expressivo do que um autômato finito? Ou existe alguma maneira de simular alternância usando outras construções?

De fato, a linguagem POSIX BRE não pode expressar todas as expressões regulares porque falta alternância. Não consegue nem reconhecer todos os idiomas finitos, muito menos todos os idiomas regulares.

Por exemplo, não é reconhecível como BRE. Para provar isso, considere qual poderia ser a forma sintática de nível superior:$\{ab, ba\}$

• Não pode ser uma das formas de caractere único, pois o idioma possui palavras com tamanho .$\gt 1$
• Não pode ser porque isso corresponderia à string vazia.$R^*$
• Não pode ser exceto com m = n = 1 (nesse caso, voltamos ao problema original) porque isso corresponderia a cadeias de diferentes comprimentos ou à cadeia vazia.$R^{\{m,n\}}$$m=n=1$
• Portanto, tem que haver concatenação: . Agora considere como a b é reconhecido: $R_1 R_2$$ab$
  • Se reconhece um b , em seguida, R 2 não deve reconhecer qualquer coisa outra coisa senão a cadeia vazia. Portanto, R 1 deve reconhecer { a b , b a } e voltamos ao problema original.$R_1$$ab$$R_2$$R_1$$\{ab,ba\}$
  • Se reconhece um , mas não um b , em seguida, R 2 deve reconhecer b . Mas, em seguida, R 1 R 2 reconhece todas as palavras da forma u b onde R 1 reconhece u , então R 1 não deve reconhecer qualquer coisa diferente de um . Não há como reconhecer b a .$R_1$$a$$ab$$R_2$$b$$R_1R_2$$u b$$R_1$$u$$R_1$$a$$ba$
  • Se reconhece nem um b nem um , em seguida, a única maneira para R reconhecer um b é se R 1 reconhece a cadeia vazia, caso em que estamos de volta ao problema original como acima, mas por R 2 neste momento.$R_1$$ab$$a$$R$$ab$$R_1$$R_2$

Quando “voltamos ao problema original”, isso significa que a única solução para encontrar um BRE reconhece o idioma é encontrar um BRE menor que possua a mesma propriedade. Esta é uma descida infinita , portanto não há BRE que possua a propriedade desejada.

Eu não acho que exista uma caracterização "legal" de linguagens reconhecíveis para BRE, por exemplo, linguagens reconhecíveis por uma classe de autômatos "legal".

$\{w w \mid w \in \{a,b\}^*\}$\(.*\)\1