Analogiczną postać mają słowa wygenerowane przez Czyli jeśli istnieje słowo wspólne dla i to w systemie Posta, na podstawie którego zostały zbudowane, istnieje słowo rozwiązujące pozytywnie problem odpowiedniości w tym systemie.
Ponieważ jednak problem odpowiedniości Posta jest nierozstrzygalny, nierozstrzygalne jest też istnienie wspólnego słowa.
Dowód nierozstrzygalności jednoznaczności gramatyki Weźmy dwa jednoznaczne języki i o rozłącznych nieterminalach, i symbolach startowych odpowiednio i Zbudujmy następującą gramatykę o symbolu startowym
plus wszystkie produkcje obu języków.
Gramatyka taka jest jednoznaczna wtedy i tylko wtedy, gdy nie istnieje słowo należące jednocześnie do i Ponieważ dla każdego systemu Posta potrafimy zbudować jednoznaczne gramatyki (poprzedni dowód), rozwiązanie problemu jednoznaczności rozwiązywałoby problem odpowiedniości Posta.
A zatem problem ten jest nierozstrzygalny.
Zobacz też parser
Przypisy
Bibliografia
Kategoria:Języki formalne