Возможность порождения формальной грамматикой произвольного перечислимого языка — различия между версиями
Filchenko (обсуждение | вклад) (часть 1) |
(нет различий)
|
Версия 04:27, 19 января 2012
Теорема: |
Язык распознается машиной Тьюринга тогда и только тогда, когда он генерируется формальной грамматикой |
Доказательство: |
Теперь недетерминированно симулирует вывод , начиная с . Каждая сентенциальная форма вывода появляется по порядку между последними двумя . Если некоторый выбор переходов ведет к терминальной строке, она сравнивается с . Если они совпадают, допускает.Формально, пусть Из этой простой симуляции выводов в имеет на ленте . передвигает недетерминированно головку по , выбирая позицию и константу между и максимальной длиной левой части любого правила вывода в . Затем проверяет подстроки . Если — левая часть некоторого правила вывода из , она может быть заменена на правую часть. может сдвинуть либо влево, либо вправо, освобождая или заполняя место, если правая часть имеет длину, отличную от . видно, что печатает на ленте строку вида , в точности, если . Если , допускает . |