Учитывая следующий язык:
Lf = { р (м) | Язык M конечен }
Лф узнаваем? если нет, докажите с помощью приведения. В противном случае создайте NDTM, который его распознает.
Я почти уверен, что Lf нельзя распознать, но я не уверен, как это доказать.
Какие-либо предложения ?
