Resolvendo problema de associação para uma linguagem gerada pelo PDA sem converter o PDA para um CFG

Question

A solução clássica para o problema de associação de uma linguagem gerada por um PDA é converter o dito PDA a um CFG e depois usar o CYK ou um algoritmo similar.Eu queria saber se há algum algoritmo conhecido para resolver este problema sem uma conversão para um CFG.

minha tentativa de uma solução ingênua foi "imitar" um PDA, mas se houver uma transição de formulário $ (Q, \ Varepsilon, A, Q, AA) $ , então a pilha cresce infinitamente e a emulação nunca pára.

Answer 1

Sim, é possível. Dada um autômato de pushdown $ P $ e uma palavra $ x $ , você pode facilmente construir um novo autômato de pushdown $ p '$ tal que $ l (p')= l (p) \ cap \ {x \} $ < / span>. Isso funciona usando uma construção de produtos para expandir o controle de estado finito da $ P $ por um fator de $ n $ < / span>, onde $ n $ é o comprimento da $ x $ .

Agora, você pode testar se $ P $ aceita qualquer palavra não vazia. Uma maneira de fazer isso é computar o conjunto de todas as configurações acessíveis da $ P $ . Este conjunto é um conjunto infinito, mas é um conjunto regular e você pode construir um automatão finito que represente o conjunto de configurações acessíveis. Uma maneira de fazer isso é usar um algoritmo para computação post *; ver Secção 2.2.2 do Técnicas de Análise Para a segurança da informação , por Anupam Datta, Sobhui, Ninghui Li, David Melski e Reps Thomas. (Você pode ver isso como uma melhoria ao algoritmo de Tomita que trabalha para PDAs arbitrárias, não apenas os que surgem de um LR (k) analisador. Os ciclos não são um problema.)

Isso pode ser moralmente isomorfo para converter $ P $ para uma gramática sem contexto, interseção dessa gramática com a linguagem regular $ \ {x \} $ Usando a construção do produto e, em seguida, usando algoritmos padrão para testar se isso gera uma linguagem não vazia. Que, por sua vez, pode ser moralmente isomorfica para converter $ P $ para uma gramática sem contexto e, em seguida, usando a análise de cyk.

O tempo de execução de todos esses métodos é $ O (n ^ 3) $ , portanto, enquanto o algoritmo parece diferente no papel, ele não leva a nenhum melhoria no tempo de execução. A abordagem baseada em PDA tem a vantagem de ser facilmente adaptada ao processamento on-the-fly da palavra $ x $ .