Questões sobre a teoria das expressões regulares, tanto no sentido da definição original de Kleene quanto das expressões regulares POSIX.
Estou pensando no seguinte problema: Quero encontrar uma expressão regular que corresponda a um conjunto específico de cadeias de caracteres (por exemplo, endereços de email válidos) e não a outros (endereços de email inválidos). Suponha que por expressão regular queremos dizer alguma máquina de...
Pergunte até a alguém com experiência em ciência da computação o que é uma expressão regular e é provável que a resposta ultrapasse a restrição de estar ao alcance de um autômato de estado finito. Por exemplo, a "expressão regular" /^1?$|^(11+?)\1+$/ criado pela notável personalidade do Perl,...
É sabido que uma expressão regular pode ser reconhecida por um autômato finito não determinístico de tamanho proporcional à expressão regular ou por uma FA determinística que é potencialmente exponencialmente maior. Além disso, dada uma string e uma expressão regular , o NFA pode testar a...
Eu queria saber se existe um algoritmo `` melhor '' (explicarei em que sentido) iniciar a partir de um DFA e construir uma expressão regular tal que , do que o livro de Hopcroft e Ullman (1979). Lá, os conjuntos são usados para representar conjuntos de seqüências de caracteres que levam o DFA do...
Por que os idiomas regulares (e a partir dessas expressões regulares) são chamados de "regulares"? Há muita regularidade também em idiomas sem contexto, outros tipos de idiomas. Suponho que, no começo, o adjetivo "regular" tenha sido usado para diferenciar esse tipo de idioma de outros idiomas...
Além da complexidade (determinística) da comunicação de uma relação R , outra medida básica para a quantidade de comunicação necessária é o número da partição do protocolo p p ( R ) . A relação entre essas duas medidas é conhecida até um fator constante. A monografia de Kushilevitz e Nisan (1997)...
É sabido que o seguinte problema está completo no PSPACE: Dada a expressão regular , ?L ( β ) = Σ ∗ββ\betaL ( β) = Σ∗L(β)=Σ∗L(\beta) = \Sigma^* E quanto a determinar a equivalência a outras expressões regulares (fixas) ?αα\alpha Dada a expressão regular , ?L ( β ) = L ( α )ββ\betaeu( β) = L...
As implementações mais modernas de expressões regulares, como as em perl ou .NET, vão além da definição clássica de ciência da computação dos REGEXes com recursos como lookahead e lookbehind. Esses recursos permitem analisar instruções que não podem ser descritas com um autômato finito e não...
Eu queria saber se a especificação JSON definiu uma linguagem regular. Parece bastante simples, mas não tenho certeza de como provar isso sozinho. A razão pela qual pergunto é porque estava pensando se alguém poderia usar expressões regulares para analisar efetivamente o JSON. Alguém com...
Vinte anos atrás, criei um pacote de expressões regulares que incluía conversões de expressões regulares em uma máquina de estado finito (DFA) e oferecia suporte a uma série de operações fechadas de expressões regulares (estrela Kleene, concatenação, reversão, operações de conjunto etc.). Eu não...
A altura da estrela (generalizada) de um idioma é o agrupamento mínimo de estrelas Kleene necessárias para representar o idioma por uma expressão regular estendida. Lembre-se de que uma expressão regular estendida sobre um alfabeto finito UMAUMAA satisfaz o seguinte: (1) e um são estendidos...
Sabe-se que minimizar o tamanho de uma expressão regular é completo no PSPACE, mesmo que tenhamos um DFA como especificação da linguagem . Quais são os resultados se o idioma for finito? Pode-se considerar esse problema em dois modelos: A entrada é todas as strings do idioma e medimos o...
Existe alguma hierarquia "legal" conhecida (pode ser finito) dentro da classe de idiomas regulares ? Por legal aqui, as classes em cada hierarquia capturam expressividade / poder / complexidade diferentes. Além disso, a composição de cada classe é "bem" demonstrada por alguns elementos...
Inspirado por esta pergunta , estou curioso sobre o seguinte: Qual é a pior complexidade possível de verificar se um determinado DFA aceita o mesmo idioma que uma determinada expressão regular? Isso é conhecido? A esperança seria que esse problema estivesse em P - que houvesse um polinômio de...
Estou interessado no problema clássico INCLUSÃO LÍNGUA REGULAR. Dada uma expressão regular , denotamos por L ( E ) a linguagem regular a ela associada. (As expressões regulares estão em um alfabeto fixo Σ , com a união de operações, estrela Kleene e concatenação.)EEEL(E)L(E)L(E)ΣΣ\Sigma Entrada:...
Todos os meus livros usam o mesmo algoritmo para produzir um DFA dado um regex: primeiro, faça um NFA que reconheça o idioma do regex e, usando a construção do subconjunto (também conhecido como "powerset"), converta o NFA em um DFA equivalente ( opcionalmente, minimizando o DFA). Também ouvi uma...
Estou tentando elaborar uma taxonomia de algoritmos para transformar expressões regulares em autômatos, a fim de executar alguns testes empíricos de suas propriedades de complexidade em domínios específicos. Estou ciente de vários nomes 'maiores', por exemplo, Thompson "Algoritmo de pesquisa...
Eu queria saber sobre quais conjuntos de idiomas são gerados por restrições de expressões regulares. Supondo que todas as restrições tenham um símbolo constante para cada elemento de e concatenação. Então, oito classes podem ser formadas pela presença ou ausência de complemento / negação, alteração...
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...
Existe um algoritmo para verificar se uma expressão regular de tamanho corresponde a uma string de tamanho , assumindo um alfabeto de tamanho fixo, se isso importa?O ( n + m )O(n+m)O(n+m)nnnmmm O algoritmo NFA padrão é pior caso de . Groz et al. obtenha tempo linear para uma variedade de classes...