Expressões regulares de famílias de expressões regulares

8

Eu estava lendo sobre o problema da altura das estrelas e notei que a família de expressões regulares de Eggan segue um padrão simples que pode ser descrito por uma expressão regular. Minha pergunta é: existem resultados interessantes sobre expressões regulares que descrevem famílias de expressões regulares? Esse processo pode ser continuado ainda mais, para que você tenha uma regex descrevendo uma família de regexes, cada uma das quais descrevendo uma família de regexes? Apenas um pensamento.

garageàtrois
fonte
1
De que tipo de descrição você está falando? As famílias de REs Eggan e Dejean-Schützenberger têm características que as tornam não regulares (parênteses de profundidade ilimitada; além disso, os índices no caso Eggan e os crescentes blocos a e b no caso DS).
Klaus Draeger

Respostas:

3

Os idiomas regulares são fechados em união, concatenação e estrela; portanto, expressões regulares em expressões regulares descrevem idiomas regulares. Portanto, regex, que descreve regex, que descreve regex ainda descreve a família de idiomas regulares, e você pode continuar esse processo pelo tempo que desejar.

(aa|b)+=R0(a|bb)+=R1(R0R1R0)(aa|b)+(aa|b)+(aa|b)+(a|bb)+(aa|b)+(aa|b)+(a|bb)+(a|bb)+(aa|b)+

LΣ|Σ|=nLσ1,Lσ2,,LσnΔwLw[i]=σjLσjw=w[1]w[2]w[k]Lw[1]Lw[2]Lw[k]comp(L,L1,,Ln). Portanto, o nível de regex sob regex é apenas o número de operações de composição que foram usadas. E idiomas regulares são fechados em operação de composição.

δδ(L)δ(L)L

Alexander Rubtsov
fonte