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?
19
Respostas:
Nós reduzir de Correspondência Problema do Post . Suponha que pode, de fato, decidir a linguagem .{ ⟨ G ⟩ | G um CFG e L ( 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, ... , βm G = ( V, Σ , R , S) V= { S, S1 1, S2} (onde σ iR = { S→ S1 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} σi são novos caracteres adicionados ao alfabeto, por exemplo, ).σi=i–
Por isso, reduzimos para PCP e, como isso é indecidível, terminamos.
(Deixe-me saber se eu fiz algo estúpido!)
fonte