Como provar que uma linguagem livre de contexto é ambígua indecidível?

19

Li em algum lugar que uma máquina de Turing não pode calcular isso e, portanto, é indecidível, mas por quê? Por que é computacionalmente impossível para uma máquina gerar a árvore de análise e tomar uma decisão? Talvez eu esteja errado e isso possa ser feito?

Ulkmun
fonte
11
Sim, você está correto, uma máquina de Turing não pode decidir se uma linguagem sem contexto é ambígua ou não, e isso pode ser reduzido a partir do problema de correspondência posterior , que é indecidível. Observe que uma árvore de análise pode ser infinitamente grande e não podemos decidir quando paramos o cálculo.
Hsien-Chih Chang #
Hsien-Chih, você está se referindo a "analisar árvores" para palavras que não estão no idioma (ou seja, análises malsucedidas) ou está tentando dizer que as árvores podem ser arbitrariamente grandes?
Raphael

Respostas:

22

Nós reduzir de Correspondência Problema do Post . Suponha que pode, de fato, decidir a linguagem .{G|G um CFG e eu(G) ambíguo}

Dado : Construa o seguinte CFG G = ( V , Σ , R , S ) : V = { S , S 1 , S 2 } , R = { S S 1 | S 2 , S 1α 1 Sα1 1,...,αm,β1 1,...,βmG=(V,Σ,R,S)V={S,S1 1,S2} (onde σ iR={SS1 1|S2,S1 1α1 1S1 1σ1 1||αmS1 1σm|α1 1σ1 1||αmσm,S2β1 1S2σ1 1||βmS2σm|β1 1σ1 1||βmσm}σisão novos caracteres adicionados ao alfabeto, por exemplo, ).σi=i_

wSS1S1S2w

SS1ασ~SS2βσ~α=βαβσ~

Por isso, reduzimos para PCP e, como isso é indecidível, terminamos.

(Deixe-me saber se eu fiz algo estúpido!)

alpoge
fonte
11
Tente \ textrm, assim: {GG um CFG e eu(G) ambíguo}
Hsien-Chih Chang