Complexidade da interseção de linguagens regulares como gramáticas sem contexto

20

Dadas as expressões regulares , existem limites não triviais no tamanho da menor gramática livre de contexto para ?R 1R nR1,,RnR1Rn

Máx.
fonte
??? tentando visualizar isso. existe algum truque? a interseção de Rn é regular. pode-se encontrar o DFA mínimo (wrt state count) através de métodos padrão, que também é um CFG.
vzn
@ vzn: você está certo. O problema é que esse DFA e, portanto, o CFG, podem ser muito grandes. Gostaria de saber se é possível usar a energia extra dos CFGs para obter uma descrição mais sucinta do cruzamento.
Max
conjectura não. suspeite que toda CFL que reconhece (ou seja, é equivalente a) uma RL não usa sua pilha ou pode ser convertida para uma que não aumenta sem estados, e o mínimo PDA (wrt state count) é do mesmo tamanho que o mínimo DFA. nunca ouvi / vi uma prova disso. talvez não seja difícil? uma pergunta mais simples, existe algum PDA que reconheça uma RL menor que o DFA? Acho que não.
vzn
@vzn: conjectura útil, mas falso: vamos Lk ser o subconjunto das línguas Dyck em dois tipos de parênteses onde a profundidade de aninhamento máxima é k . Existe um CFG para Lk de tamanho O(k) , mas o DFA mínimo (até, eu acho, o NFA mínimo) tem tamanho O(2k) .
Max
Linguagens dyck são CFLs, mas não RLs ...? mas veja se você está limitando a profundidade máxima de aninhamento ... então, você pode criar o mesmo idioma com interseções RL? qual / onde está a prova de que o DFA mínimo é tão grande? é que afirma ? você não define um critério de minimalidade ou em outro lugar e considera os estados como um caso natural, mas geralmente não é o único. O(2k)
vzn

Respostas:

6

Essa é uma ótima pergunta e realmente está dentro dos meus interesses. Fico feliz que você pediu Max.

Seja DFA com no máximo O ( n ) estados cada um. Seria bom se existisse um PDA com subexponencialmente muitos estados que aceitassem a interseção dos idiomas do DFA. No entanto, sugiro que esse PDA nem sempre exista.nO(n)

Considere o idioma da cópia. Agora, restrinja-o a copiar cadeias de comprimento n.

Formalmente, considere -copy : = { x xn:= .{xx|x{0,1}n}

Podemos representar -copy como a interseção de n DFA do de tamanho no máximo O ( n ) . No entanto, o menor DFA que aceita n -copy possui 2 Ω ( n ) estados.nnO(n)n2Ω(n)

Da mesma forma, se nos restringirmos a um alfabeto de pilha binária, suspeito que o menor PDA que aceita -copy exponencialmente tenha muitos estados.n

PS Sinta-se livre para me enviar um e-mail se você gostaria de discutir mais. :)

Michael Wehar
fonte
5

Não acho que possa haver limites inferiores ou superiores não triviais.
Para limites inferiores, considere o idioma para um k fixo . O tamanho da menor gramática livre de contexto é logarítmica no tamanho de L 1 de expressão regular, ao passo que o tamanho da menor autómato para L 1 é linear no intervalo de tamanho de L 1 de expressão regular. Essa diferença exponencial permanece a mesma se cruzarmos L 1 com outros idiomas. Para limites superiores, considere um idioma L 2 que consiste em exatamente umL1={a2k}kL1L1L1L1
L2deBruijn-Sequence of length . Sabe-se que o tamanho de uma gramática menor para L 2 é o pior caso, ou seja, O ( nnL2, então a diferença para o menor autômato paraL2é simplesmente um fator logarítmico, a proposição 1 emO(nlogn)L2

Um limite inferior ou superior geral não trivial contraria esses resultados, pois o que é verdadeiro para a interseção de idiomas deve ser verdadeiro para a interseção de 1 idioma.n1

john_leo
fonte
A observação sobre o tamanho da menor gramática para a única deBruijn-Sequence é bastante interessante. Poderia, por favor, fornecer uma referência. Obrigado.
Michael Wehar
Além disso, eu poderia estar enganado, mas parece que você resolveu o problema apenas para uma única expressão regular (em vez de um produto de expressões regulares)?
Michael Wehar
@ MichaelWehar Sim, eu considerei apenas uma única expressão regular. Porque, se deve ser verdade para a interseção de idiomas, certamente deve ser verdade para a interseção trivial. Não sei como reformular a questão para excluir esses casos. Eu adicionei a referência, deveria ter feito isso imediatamente, desculpe. n
john_leo
1
Obrigado! Você conseguiu descrever um exemplo específico. Aqui está uma observação simples que leva à existência de tais exemplos. Seja n dado. Existem 2 ^ n cadeias de comprimento n. Além disso, não há mais que 2 ^ n máquinas de Turing com no máximo n / log (n) estados. Portanto, alguma string x de comprimento n tal que nenhuma máquina de Turing com menos de n / log (n) estados aceite o idioma {x}. Portanto, {x} é aceito por um DFA com n estados e não pode ser aceito por um PDA com menos de n / log (n) estados.
Michael Wehar
5

Deixe-me segundo o julgamento de Michael, esta é realmente uma pergunta interessante. A idéia principal de Michael pode ser combinada com um resultado da literatura, fornecendo assim um limite inferior semelhante com uma prova rigorosa.

Vou me referir aos limites do tamanho do CFG em termos do número total de símbolos alfabéticos nas expressões regulares. Seja esse número indicado por k . (Como observou john_leo, não encontraremos limites úteis em termos do número de expressões regulares que participam da interseção.)nk

2k+12k+1sO(s2)O(4k)

2Ω(k/logk)

Ln={wwRw{a,b}|w|=n}wRwLn2n+1

  • ri=(a+b)ia(a+b)2(ni1)a(a+b)+(a+b)ib(a+b)2(ni1)b(a+b)1in
  • si=(a+b)a(a+b)2(ni1)a(a+b)i+(a+b)b(a+b)2(ni1)b(a+b)i1in
  • =(a+b)3n

kO(n2)

Ln2n/(2n)=2Ω(k/logk)2nnn/(2n)

O(4n)

Referências:

Hermann Gruber
fonte