Dureza de encontrar uma palavra de comprimento no máximo

10

Declaração do problema:

Seja M um autômato pushdown (potencialmente não determinístico) e seja A seu alfabeto de entrada. Existe uma palavra wA st |w|k que é aceito por M ?

Esse problema está completo? Foi estudado? Existe um algoritmo que permita encontrar essa palavra?

Lamine
fonte
O algoritmo de Djikstra não deveria fazer o truque? (Estou muito provavelmente mal-entendido alguma coisa aqui!)
alpoge
"comprimento no máximo "? k
precisa saber é o seguinte
De nada, Kaveh. Sim, esqueci "no máximo", editei novamente.
Lamine
11
A resposta é fácil - essa é uma pergunta de lição de casa?
Sariel Har-Peled
Temos acesso à descrição dos autômatos ou apenas como caixa preta?
Raphael

Respostas:

9

Calcule a interseção do seu idioma CFG com o idioma normal (isso significa multiplicar o número de estados por ke adicionar um estado "sem saída"). Agora verifique se o resultado está vazio: converta em gramática (acho que o resultado terá tamanho polinomial) e "retorne" das produções epsilon.i=0kAkk

Edit: Kaveh mencionou que isso é polinomial em , então se kkk é dado como entrada, o algoritmo é exponencial em . No entanto, Kaveh encontrou uma maneira de corrigi-lo. Converta o autômato original em um CFG e substitua todos os terminais por um terminal fixo. Agora use um algoritmo iterativo para encontrar o tamanho mínimo de uma palavra gerada por cada não-terminal, conforme a seguir.|k|

Inicialize todos os comprimentos com e atualize iterativamente todos os comprimentos da maneira óbvia: dada uma produção A a tB i (a ordem não importa), coloque f ( A ) = min ( f ( A ) , t + f ( B i ) ) . Reivindicação: isso converge emAatBif(A)=min(f(A),t+f(Bi)) iterações, onde nO(n)né o número de não terminais. O motivo é que, em uma árvore que gera a palavra de tamanho mínimo, nenhum não terminal é usado duas vezes; cada "aresta" leva no máximo uma iteração para processar (algumas arestas podem ser "atualizadas" em paralelo).

Yuval Filmus
fonte
Eu também acho que a transformação PDA CFG é polinomial. Obrigado! Portanto, o problema está em P . P
Lamine
Ok, já que existe uma maneira de calcular diretamente o menor comprimento, não é uma entrada. Mas não entendo por que substituir todos os terminais por um fixo. O algoritmo deve operar corretamente com os terminais originais. |k|
Lamine
Você está certo, isso realmente não importa.
Yuval Filmus
5

Altere todos os caracteres do alfabeto para um único caractere específico. Agora, você tem o PDA definido sobre um único caractere. Sua linguagem é uma gramática livre de contexto. No entanto, a gramática livre de contexto sobre um único caractere é regular. Portanto, converta o CFG em um idioma comum e verifique se ele contém uma palavra de comprimento k.

Agora, todas essas conversões tendem a exigir tempo exponencial, mas me parece improvável que o problema esteja completo. Especialmente se você permitir o tempo polinomial em .k

Posso estar errado e peço desculpas pela minha resposta inicial ...

Aliás, o fato de um CFG sobre uma única letra ser regular segue o teorema de Parikh. Embora uma prova direta não seja muito difícil. Veja o link para obter mais detalhes sobre o teorema de Parikh - é um resultado bonito ... http://www8.cs.umu.se/kurser/TDBC92/VT06/final/3.pdf

Sariel Har-Peled
fonte
Não, eu não sou estudante. O problema que mencionei é inicialmente um problema de rede que foi modelado como um autômato. Eu apenas saberia se vale a pena procurar uma solução polinomial ou não.
Lamine
5
Esta resposta não deve ser um comentário?
precisa saber é o seguinte
2
Sim deveria. Sariel, você poderia mudar isso para um comentário ou fornecer uma resposta?
Suresh Venkat
@Suresh: Você pode estar ciente disso, mas agora os moderadores podem transformar uma resposta em um comentário .
Tsuyoshi Ito 21/01
Mudei a resposta original para um comentário. Esta é uma nova resposta.
Suresh Venkat
0

Um método provavelmente subótimo: execute o algoritmo de Djikstra. Então, para cada estado final, compare as distâncias com . Se algum for kkk , aceite. Rejeitar.

EDIT: O acima funciona apenas para NFAs! Me desculpe por isso.

alpoge
fonte
(mas definitivamente poli-tempo!)
alpoge
Não tenho certeza de que o algoritmo de Dijkstra possa resolver o problema. Pode encontrar o caminho mais curto entre o estado inicial e o final. Obviamente, uma palavra que pode ser aceita por esses caminhos pode ser gerada. Mas esses caminhos são elementares e as palavras podem ser aceitas por caminhos não-complementares; caso contrário, o problema de determinar se uma gramática livre de contexto pode gerar qualquer palavra seria decidível, mas não é.
Lamine
O teste de vazio para lâmpadas fluorescentes compactas é decidível, não?
precisa saber é o seguinte
(Perdoe-me novamente se eu sou mal-entendido!)
alpoge
Bem, pode-se usar um algoritmo de 'marcação' para fazer isso (dado o CFG) - marcar terminais, depois marcar coisas que derivam terminais, depois marcar coisas que derivam coisas marcadas etc. até o término do processo e, em seguida, verificar se a variável inicial estiver marcada. Além disso, ignore minha resposta - é isso que você deve fazer por um NFA (certamente não por um PDA!).
precisa saber é o seguinte