É 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 associação em tempo proporcional a, e o DFA pode testar a associação no tempo proporcional a. A desaceleração da NFA decorre do fato de que precisamos rastrear os conjuntos de estados possíveis em que o autômato pode estar, e a explosão exponencial do DFA decorre do fato de que seus estados são elementos do conjunto de potências dos estados da região. NFA.
É possível eficientemente (ou seja, em tempo melhor que e espaço melhor que ) reconhecer expressões regulares, se permitirmos o uso de máquinas mais poderosas do que autômatos finitos? (Por exemplo, existem ganhos sucintos no reconhecimento de idiomas regulares com autômatos de empilhamento ou máquinas de contagem?)
fonte
Respostas:
É fácil o suficiente para trocar o tempo pelo espaço, da seguinte maneira.
Converter a expressão regular a um NFA - para concretude em algoritmos de comparação, vamos supor que é o número de estados NFA, de modo que o seu O ( r s ) tempo ligado para simular diretamente o NFA é válido e seu O ( 2 r ) o espaço vinculado para executar o DFA convertido também é válido sempre que você estiver trabalhando em uma RAM que pode endereçar essa quantidade de memória.r O(rs) O(2r)
Agora, particione os estados do NFA (arbitrariamente) em subconjuntos S i de no máximo ⌈ r / k ⌉ estados cada. Dentro de cada subconjunto S i , podemos indexar os subconjuntos A i de S i por números de 0 a 2 ⌈ r / k ⌉ - 1 .k Si ⌈r/k⌉ Si Ai Si 0 2⌈r/k⌉−1
Construir uma tabela em que i e j são na gama de 0 a k - 1 , c é um símbolo de entrada, e um i é (o índice numérico de) um subconjunto de S i . O valor armazenado na tabela é (o índice numérico de) um subconjunto de S j : um estado y está em T [ i , j , c , A i ] se e somente seT[i,j,c,Ai] i j k−1 c Ai Si Sj y T[i,j,c,Ai] pertence a S j e há um estado em A i que faz a transição para y no símbolo de entrada c .y Sj Ai y c
Para simular o NFA, manter índices, um para cada S i , especificando o subconjunto Um i dos estados em S i que podem ser alcançados por alguns prefixo da entrada. Para cada símbolo de entrada c , utilizar as tabelas de olhar para cima, para cada par i , j , o conjunto de estados em S j que pode ser alcançado a partir de um estado em A i por uma transição em c , e, em seguida, usar um binário bit a bit ou operação nos índices numéricos desses conjuntos de estados para combiná-los em um único subconjunto de estados de S jk Si Ai Si c i,j Sj Ai c Sj . Portanto, cada etapa da simulação leva tempo , e o tempo total para a simulação é O ( s k 2 ) .O(k2) O(sk2)
O espaço necessário é o espaço para todas as tabelas, que é . A análise de tempo e espaço é válida em qualquer RAM que possa endereçar tanta memória e que possa executar operações binárias em palavras grandes o suficiente para endereçar essa quantidade de memória.O(k22r/k)
A troca de tempo e espaço que você obtém disso não corresponde perfeitamente à simulação da NFA, devido à dependência quadrática de . Mas então, eu sou cético de que O ( r s ) é o momento certo com destino a simulação NFA: como você simular um único passo da NFA mais rápido do que olhar para todos os (possivelmente de forma quadrática muitos) transições permitida de um momento estado ativo para outro estado? Não deveria ser O ( r 2 s ) ?k O(rs) O(r2s)
De qualquer forma, deixando variar, é possível obter limites de tempo em um continuum entre os limites do DFA e do NFA, com menos espaço que o DFA.k
fonte
Esta não é uma resposta, mas é muito longa para um comentário. Estou tentando explicar por que a pergunta, como colocada, pode ser difícil de entender.
Há duas maneiras de definir complexidade computacional de um dispositivo X .
O primeiro e mais natural caminho é intrínseco . É preciso dizer como o dispositivo X usa a entrada, para que possamos ver mais tarde como o tamanho n da entrada afeta o tempo de execução do dispositivo. É preciso também dizer o que conta como uma operação (ou etapa ). Simplesmente deixamos o dispositivo rodar nas operações de entrada e contagem.
O segundo é extrínseco . Nós definimos complexidade computacional para um outro dispositivo de Y e, em seguida, programar Y para actuar como um simulador para X . Como pode haver várias maneiras de Y simular X , precisamos acrescentar que devemos usar a melhor. Deixe-me dizer o mesmo com outras palavras: Dizemos que X leva tempo em uma entrada de tamanho n se existe um simulador de X implementado na máquina Y que leva tempo f ( n ) .O(f(n)) f(n)
Por exemplo, uma definição intrínseca para a NFA diz que são necessárias n etapas para processar uma sequência de comprimento n ; uma definição extrínseca que usa uma máquina de RAM como dispositivo Y diz que o limite superior mais conhecido é provavelmente o que David Eppstein respondeu. (Caso contrário, seria estranho que (1) a melhor implementação prática apontada na outra resposta não use a melhor alternativa e (2) ninguém aqui indicou uma alternativa melhor.) Observe também que falando estritamente o seu dispositivo X é a expressão regular , mas como o NFA tem o mesmo tamanho, é seguro aceitá-lo como o dispositivo X que você está vendo.
Agora, quando você usa o segundo tipo de definição, faz pouco sentido perguntar como a restrição dos recursos do dispositivo X afeta o tempo de execução. No entanto, faz sentido perguntar como a restrição dos recursos do dispositivo Y afeta o tempo de execução. Obviamente, permitir máquinas mais poderosas Y pode simular o X mais rapidamente. Portanto, se assumirmos uma das máquinas mais poderosas que podem ser implementadas (isso exclui as máquinas não determinísticas, por exemplo) e apresentarmos um limite mais baixo , sabemos que nenhuma máquina menos poderosa poderia fazer Melhor.Ω(f(n))
Portanto, de certa forma, a melhor resposta que você poderia esperar é uma prova em algo como o modelo de sonda celular que simular um NFA precisa de um certo tempo. (Observe que, se você levar em consideração a conversão NFA em DFA, precisará de tempo para anotar o grande DFA; portanto, a memória não é o único problema.)
fonte
Mesmo que você acredite que não há nada novo ou velho a ser aprendido sobre a correspondência de expressões regulares, confira um dos artigos mais bonitos que já encontrei há muito tempo: uma peça sobre expressões regulares de S Fischer, F Huch e T Wilke, ICFP 2010.
(MMT Chakravarty merece o crédito por recomendar este documento.)
EDIT: A razão pela qual este artigo é relevante é que ele descreve uma nova técnica (baseada em Glushkov dos anos 60) que evita a construção da NFA completa (e muito menos da DFA) correspondente à ER. Em vez disso, o que é feito se assemelha à execução de um algoritmo de marcação semelhante ao conhecido para decidir a aceitação de uma palavra por um NFA na árvore de sintaxe do ER. As medições de desempenho sugerem que isso é competitivo, mesmo com a biblioteca re2 publicada recentemente pelo Google.
fonte
Dê uma olhada neste artigo de Russ Cox. Ele descreve uma abordagem baseada em NFA, empregada pela primeira vez por Ken Thompson, pela qual uma sequência de entrada s pode ser correspondida a uma expressão regular r no tempo O (| s |. C ) e no espaço O (| r |. D ), em que c e d são constantes de limite superior. O artigo também detalha uma implementação em C da técnica.
fonte