Какие из следующих трех автоматов С1 , С2 , С3 распознают язык, представляемый регулярным выражением 0(10 +1)*?

С1 = < {0,1}, {q, p, r, s, t}, q, F1={ t }, Φ1>,

С2 = < {0,1}, {q, p, r, s }, q, F2={p, r}, Φ2>,

С3 = < {0,1}, {q, p, r, s, t}, q, F3={ p, r, s}, Φ3>,

где программы заданы в следующих таблицах (∅ означает отсутствие соответствующего перехода).

Правильный ответ:

• # В теореме 20.5 была доказана неразрешимость проблемы останова: по произвольной структурированной программе П определить завершится ли вычисление П на входе 0. Пусть Mh0= {n | ФПn,y (0) < ∞} – это (неразрешимое) множество номеров программ, которые останавливаются на входе =0. Рассмотрим проблему определения по структурированной программе монотонности вычисляемой ею функции: M mon = {n | для любых x1 и x2, если x1 < x2, то ФПn,y (x1) < ФПn,y (x2)}. Какие из следующих функций сводят Mh0 к M mon ? f1(n) = номер программы: 'xn:=x; x:= 0; Пn ; y:= xn'. (здесь переменная xn не входит в Пn ) f2(n) = номер программы: 'Пn ; y:= x'. f3(n) = номер программы: 'y:= x; x:= 0; Пn ; y:= y+1'.
• # Пусть язык L в алфавите {a, b, c}, состоит из всех слов, в которых количество букв b превосходит количество букв a не менее чем на 3. Предположим, что L автоматный язык и что n – это константа, которая существует для него по утверждению теоремы о разрастании. Какое из следующих "специальных" слов позволяет опровергнуть это предположение, т.е. для какого из них не выполнено утверждение 3 теоремы о разрастании?
• # Пусть П× - это программа, которая вычисляет функцию Ф× (x,y) = x·y в переменной x, используя две рабочих переменных z и i Какие из следующих структурированных программ П1, П2, П3 вычисляют в переменной x двоичный логарифм от x, т.е. функцию [ log2( x)]? [Большая Картинка]
• # Обозначим через minus(x,y) функцию "усеченного" вычитания, равную (x – y) при x ≥ y и 0 – в противном случае. Для какой из следующих функций f(x,y) выражение μy [ f(x,y)= 0] задает функцию (целая часть квадратного корня из x) ?
• # Три машины Тьюринга Mi = < Σ, Q !, Pi, q, !> (i = 1,2, 3), имеют общий алфавит ленты Σ={ ∧, a, b}, алфавит состояний Q = { q, p, r, s, !}, начальное состояние q, заключительное состояние ! и следующие программы: [Большая Картинка] Какие из этих машин переводят любую начальную конфигурацию вида q an b в заключительную конфигурацию ! b an (n ≥ 0 )?