O POSIX BRE pode expressar todos os idiomas comuns?

13

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?

Steve Kobes
fonte

Respostas:

17

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:{umab,buma}

  • Não pode ser uma das formas de caractere único, pois o idioma possui palavras com tamanho .>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: R1R2umab
    • 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.R1umabR2R1{umab,buma}
    • 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 .R1umaumabR2bR1R2vocêbR1vocêR1umabuma
    • 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.R1umabumaRumabR1R2

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".

{WWW{uma,b}}\(.*\)\1

Gilles 'SO- parar de ser mau'
fonte
1
Se você estiver usando uma ferramenta como grep, que pode aceitar várias expressões separadas por nova linha, é usar o produto cartesiano de todas as possíveis alternâncias (por exemplo, {ab, ba} {ab, ba} se tornando {abba, abba, baab, baba}) suficiente para ser equivalente a qualquer "BRE-mais-alternação" e, portanto, a qualquer linguagem regular?
usar o seguinte código
1
@ Random832: Tente fazer (abc|bac)*.
rici 28/08