prosze o pomoc, bo za 3 dni kolokwium, a ja nie wiem jak zabrac sie za te zadania
Moze bedzie ktos tak dobry i wytlumaczy mi o co w tym chodzi:1. Pokazac, ze problem równowaznosci gramatyk bezkontekstowych (typ-2) jest nierozstrzygalny, tzn. nie istnieje algorytm, który dla dowolnych dwóch gramatyk bezkontekstowych nad alfabetem \(\displaystyle{ \sum_{}^{}}\)= {a, b} rozstrzyga, czy gramatyki te generuja ten sam jezyk. (Uwaga: problem równowazmosci dla gramatyk regularnych jest rozstrzygalny.)
2. Pokazac, ze problem pustosci gramatyk kontekstowych (typ-1) jest nierozstrzygalny, tzn. nie istnieje algorytm, który dla dowolnej gramatyki kontekstowej nad alfabetem \(\displaystyle{ \sum_{}^{}}\) = {a, b} rozstrzyga, czy gramatyka ta generuje jezyk pusty. (Uwaga: problem pustosci dla gramatyk bezkontekstowych jest rozstrzygalny.)
3. Czy istnieje maszyna Turinga (z lub bez własnosci stopu), która dla zadanej maszyny M potrafi
powiedziec, czy istnieje maszyna M' z własnoscia stopu taka, ze L(M) = L(M').