Expressões regulares “densas” geram

25

Aqui está uma conjectura para expressões regulares:

Para a expressão regular , deixe o comprimento | R | seja o número de símbolos nele, ignorando parênteses e operadores. Por exemplo | 0 1 | = | ( 0 1 ) | = 2R|R||01|=|(01)|=2

Conjectura: se e L ( R ) contém todas as cadeias de comprimento | R | ou menos, então L ( R ) = Σ .|R|>1L(R)|R|L(R)=Σ

Ou seja, se é 'densa' até R length 's, em seguida, R realmente gera tudo.L(R)RR

Algumas coisas que podem ser relevantes:

  1. Apenas uma pequena parte de é necessária para gerar todas as strings. Por exemplo, em binário, R = ( 0 1 ) *S vão trabalhar para qualquer S .RR=(01)SS
  2. Precisa haver uma estrela Kleene em em algum momento. Se não houver, ele perderá uma sequência de tamanho menor que | R | .R|R|

Seria bom ver uma prova ou contra-exemplo. Existe algum caso em que obviamente está errado que eu perdi? Alguém já viu isso (ou algo semelhante) antes?

Lucas Cook
fonte
são e contados como ou como ? εsymbolsoperations
Ran G.
@Ran eu estava contando eles como símbolos.
Lucas Cook

Respostas:

34

Sua conjectura é contestada por Keith Ellul, Bryan Krawetz, Jeffrey Shallit e Ming-wei Wang em seu artigo "Expressões regulares: novos resultados e problemas em aberto". Enquanto o jornal não está disponível on-line, é uma palestra .

|alph(R)|Rϵϵ|alph(R)|

n3O(n){0,1}Ω(2nn)

Yuval Filmus
fonte
Resultado muito legal, e bastante surpreendente também :) #
Alex ten Brink
Como é a expressão regular?
svick
(a+b)(c+d)=ac+bc+ad+bd
@Yuval Muito legal. Obrigado pela referência!
Lucas Cozinhe
2
@YuvalFilmus Parece que o artigo está disponível online agora.
Anton Trunov