Perguntas sobre expressões regulares, um formalismo para descrever linguagens regulares.
Converter expressões regulares em NFA (mínimo) que aceitam o mesmo idioma é fácil com algoritmos padrão, por exemplo, o algoritmo de Thompson . A outra direção parece ser mais entediante e, às vezes, as expressões resultantes são confusas. Quais algoritmos existem para converter NFA em expressões...
Como visto nesta faixa recente do XKCD e nesta postagem recente no blogde Peter Norvig (e uma história do Slashdot com o último), "regex golf" (que pode ser chamado de problema de separação de expressões regulares) é o quebra-cabeça de definir a expressão regular mais curta possível que aceita...
Esta pergunta foi migrada do Stack Overflow porque pode ser respondida no Computer Science Stack Exchange. Migrou há 7 anos . Criei uma expressão regular simples lexer e analisador para obter uma expressão regular e gerar sua árvore de análise. Criar um autômato de estado...
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 ) ∗ | = 2RRR| R ||R||R|| 0∪1 | = | (0∪1 )∗| =2|0∪1|=|(0∪1)∗|=2|0 \cup 1| = |(0 \cup 1)^*|...
Procurei na net uma resposta para essa pergunta e parece que todo mundo sabe implicitamente a resposta, exceto eu. Presumivelmente, isso ocorre porque as únicas pessoas que se importam são aquelas que tiveram educação superior sobre o assunto. Eu, por outro lado, fui jogado no fundo do poço por um...
Como o título diz, passei algumas horas no final de semana passado tentando me convencer sobre a classe de idiomas correspondida por expressões regulares compatíveis com Perl, excluindo qualquer operador correspondente que permita executar código arbitrário dentro do padrão . Se você não sabe o...
Configuração: expressões regulares com referências anteriores idioma unário (alfabeto de 1 símbolo) O seguinte problema é decidível nessa configuração: Dada uma expressão regular com referências anteriores, ela define um idioma regular? Por exemplo, (aa+)\1define um idioma regular, enquanto...
Se eu tenho uma gramática tipo 3, ela pode ser representada em um autômato de empilhamento (sem fazer nenhuma operação na pilha) para que eu possa representar expressões regulares usando linguagens livres de contexto. Mas eu posso saber se uma gramática do tipo 3 é , L L ( 1 ) , S L R ( 1 ) , etc.,...
Aparentemente, os ataques ReDos exploram características de algumas expressões regulares (de outra forma úteis) ... essencialmente causando uma explosão de caminhos possíveis através do gráfico definido pela NFA. É possível evitar esses problemas escrevendo uma regex 'não-má' equivalente? Se não...
Descobri que, se não entendo a etimologia por trás de um termo cs / programação, isso geralmente significa que perdi ou entendi mal algum conceito subjacente importante. Não entendo por que a estrela Kleene também é chamada de encerramento Kleene. Está relacionado a fechamentos na programação, uma...
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...
Eu estava brincando no outro dia neste site: http://regexcrossword.com/ e isso me fez pensar em qual seria a melhor maneira de resolvê-lo. Você pode resolver o seguinte problema em tempo polinomial ou é NP-difícil? Dada uma grade NxM com N expressões regulares para as colunas e M para as...
O problema Não há uma maneira fácil de obter uma permutação com um regex. Permutação: Obtendo uma palavra ("aabc") para outra ordem, sem alterar o número ou o tipo de letras.w=x1…xnw=x1…xnw=x_1…x_n Regex: expressão regular. Para verificação: "Permutações de regex sem repetição" A resposta...
Eu sou novo em autômatos e recebi uma breve introdução às expressões regulares apenas ontem. Eu li as várias regras para definir uma expressão regular. Mas não sou capaz de diferenciar expressões regulares e gramática de um idioma (não aprendi a gramática para expressões regulares). Entendo que a...
O objetivo é criar o DFA a partir de uma expressão regular e o uso de "Exp regular> NFA> conversão do DFA" não é uma opção. Como alguém deveria fazer isso? Fiz essa pergunta ao nosso professor, mas ele me disse que podemos usar a intuição e se recusou a fornecer qualquer explicação. Então,...
Eu pensei que todos os idiomas regulares pudessem ser expressos com expressões regulares (se um idioma for regular, pode ser expresso com regex), mas me disseram que você precisa das três operações regulares (concatenação, união e estrela) para isso segurar. Por exemplo, me disseram que se eu...
Desejo converter uma expressão regular inserida pelo usuário em um NFA, para que eu possa executar o NFA em uma string para fins de correspondência. Qual é a máquina mínima que pode ser usada para analisar expressões regulares? Suponho que deve ser um autômato push down, porque a presença de...
Dadas duas expressões regulares arbitrárias, existe um algoritmo "eficiente" para determinar se elas correspondem ao mesmo conjunto de cadeias? De maneira mais geral, podemos calcular o tamanho da interseção dos dois conjuntos de correspondências? Quais algoritmos existem para fazer isso e em que...
No trabalho, fui encarregado de deduzir algumas informações de tipo sobre uma linguagem dinâmica. Reescrevo seqüências de instruções em letexpressões aninhadas , da seguinte maneira: return x; Z => x var x; Z => let x = undefined in Z x = y; Z => let x = y in Z if x then T else F; Z =>...
Uma expressão regular é definida recursivamente como aaa para algunsa∈Σa∈Σa \in \Sigma é uma expressão regular, εε\varepsilon é uma expressão regular, ∅∅\emptyset é uma expressão regular, (R1∪R2)(R1∪R2)(R_1 \cup R_2) ondeR1R1R_1 eR2R2R_2 são expressões regulares é uma expressão...