☰

É possível egrepar essas expressões simétricas em {0,1}

tag-icon • tag-icon grep
É possível egrepar essas expressões simétricas em {0,1}

O objetivo é usar apenas egrep para combinar expressões ondenocorrências de 0 são seguidas exatamente pornocorrências de 1 e onde nenhum 0 segue um 1.

por exemplo

01
000111
000000111111

mas não:

001
011
00011

etc.

Intuitivamente, isso não parece possível porque as expressões correspondentes não têm comprimento fixo. Mas talvez esteja faltando um recurso do egrep que poderia ser útil com isso?

Responder1

Visão geral rápida de alguns conceitos de CS:

  • Autômatosaceitar strings que pertencem a uma "linguagem",gerado por uma "gramática".
  • Expressões regulares (em teoria) são equivalentes a (determinísticas ou não determinísticas)autômatos finitos(DFA/NFA). Portanto, dado um regex como 0*1*, existem DFA e NFA que podem aceitar strings correspondentes a esse regex.
  • Autômatos finitos são estritamente menos poderosos queautômatos de empilhamento(PDA). A classe de linguagens que o PDA aceita é gerada porgramáticas livres de contexto (CFG).
  • As strings que você está vendo - - são geradas pelo CFG: (vagamente, dada uma string inicial, você pode gerar uma string com e para qualquer lado da string original, ou nada - então permite gerar , , etc. ).0n1nS -> 0S1 | ε01010011

Embora o grep (estendido ou não) tenha recursos que vão além das "expressões regulares" mencionadas acima, como referências anteriores, não acredito que nenhum deles o estenda para ser tão poderoso quanto um PDA.

Pode-se provar que S -> 0S1 | εnão é regular usandoo lema do bombeamento, mas não tenho provas de que os recursos do grep o tornem capaz (ou não) de aceitar CFGs. No entanto, o artigo da Wikipédia sobreExpressões regularestem isto a dizer (negrito meu):

Muitos recursos encontrados em praticamente todas as bibliotecas modernas de expressões regulares fornecem um poder expressivo que excede em muito as linguagens regulares. Por exemplo, muitas implementações permitem agrupar subexpressões com parênteses e recuperar o valor que elas correspondem na mesma expressão (referências anteriores). Isto significa que, entre outras coisas, um padrão pode corresponder a sequências de palavras repetidas como "papa" ou "WikiWiki", chamadas de quadrados na teoria da linguagem formal. O padrão para essas strings é (.+)\1.

A linguagem dos quadrados não é regular,nem é livre de contexto, devido ao lema do bombeamento. No entanto, a correspondência de padrões com um número ilimitado de referências anteriores, suportada por inúmeras ferramentas modernas, ainda é sensível ao contexto. [33]

[33]: Cezar Câmpeanu e Kai Salomaa, e Sheng Yu (dezembro de 2003). "Um estudo formal de expressões regulares práticas". Jornal Internacional de Fundamentos da Ciência da Computação. 14 (6): 1007–1018. doi:10.1142/S012905410300214X. Teorema 3 (p.9)

Então, eu diria que é seguro dizer grepque não pode corresponder sozinho.0n1n

informação relacionada