Главная /
Введение в схемы, автоматы и алгоритмы /
4. Пусть задан ДКА A =< {a, b}, {Q, P, R, S}, Q, F= {P, S}, ΦA > с программой ΦA: { Q a → R, Q b → P, P b → S, P a → P, R a → R, R b → S, S a → S, S b → R} и гомоморфизм h: {0, 1, 2}* → {a, b}*: h(0) = bab, h(1) = aa, h(2) = ε. Какие из сле
4.
Пусть задан ДКА A =< {a, b}, {Q, P, R, S}, Q, F= {P, S}, ΦA > с программой ΦA: { Q a → R, Q b → P, P b → S, P a → P, R a → R, R b → S, S a → S, S b → R} и гомоморфизм h: {0, 1, 2}* → {a, b}*: h(0) = bab, h(1) = aa, h(2) = ε. Какие из следующих трех автоматов С1, С2, С3 распознают гомоморфный прообраз h-1(LA)?
С1 = < {0, 1}, { Q, P, R, S }, 0, F1={P, S}, Φ1>,
С2 = < {0, 1}, { Q, S }, 0, F2={ S }, Φ2>,
С3 = < {0, 1}, { Q, R, S }, 0, F3={ S }, Φ3>,
где программы заданы в следующих таблицах.
вопрос
Правильный ответ:
только
C1
только
C2
только
C3 C1и C2 C1и C3 C2и C3
все
Сложность вопроса
66
Сложность курса: Введение в схемы, автоматы и алгоритмы
92
Оценить вопрос
Комментарии:
Аноним
Кто ищет данные тесты с интуитом? Это же совсем для даунов
24 дек 2020
Аноним
Экзамен сдан на 4. лол
10 окт 2017
Другие ответы на вопросы из темы алгоритмы и дискретные структуры интуит.
- # Согласно тезису Тьюринга-Черча язык структурированных программ является универсальным – для любой вычислимой функции в нем имеется вычисляющая ее программа. Всякий язык программирования, в котором выразимы все операторы языка структурированных программ, также является универсальным. Некоторые из операторов языка структурированных программ оказываются "лишними" - они выразимы через остальные, т.е. язык сохраняет универсальность и при их удалении. Определите, какие из следующих видов операторов (по отдельности) можно выразить через остальные операторы языка. (a) x := x +1,(b) пока x < y делай P все,(c) пока x = y делай P все. .
- # Пусть S={aaa, aba, baa, bba} Какая из следующих фраз описывает итерацию S* этого языка?
- # Пусть структурированная программа P: x:= y+1; y := u+1; v := z+1; если x < v то если x = y то z := y+1 иначе z := x конец иначе z :=x +1 конец начинает работу в состоянии σ : σ(x) =0, σ(y) =3, σ(z) =5, σ(u) = 4, σ(v) =2В каком из следующих состояний σ1 она завершит свою работу?
- # Пусть П× - это программа, которая вычисляет функцию Ф× (x,y) = x·y в переменной x, используя две рабочих переменных z и i Какие из следующих структурированных программ П1, П2, П3 вычисляют в переменной x квадратный корень из x, т.е. функцию [ x 1/2]? [Большая Картинка]
- # Три машины Тьюринга Mi = < Σ, Q !, Pi, q, !> (i = 1,2, 3), имеют общий алфавит ленты Σ={ ∧, a, b}, алфавит состояний Q = { q, p, r, s, !}, начальное состояние q, заключительное состояние ! и следующие программы: [Большая Картинка] Какие из этих машин переводят любую начальную конфигурацию вида q a2n b в заключительную конфигурацию ! b an (n ≥ 0 )?