Обозначим через minus(x,y) функцию "усеченного" вычитания, равную (x – y) при x ≥ y и 0 – в противном случае. Для какой из следующих функций f(x,y, i) выражение μi [ f(x,y,i)= 0] задает функцию F(x,y) = [ y/x ] (целая часть частного от деления y на x) ?

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

• # [Большая Картинка] Какая из следующих формул задает булеву функцию, которую реализует эта диаграмма?
• # Следующий конечный автомат - преобразователь MINUS= <ΣX ={0, 1} ΣY= { 0, 1}, Q ={ 0, 1, 2, 3 }, 0, Φ, Ψ>, где [Большая Картинка] вычитает из входного двоичного числа x некоторую константу c и выдает при c ≤ x выходное двоичное число y = x –c Чему равна эта константа c?
• # На следующем рисунке представлены диаграммы двух конечных автоматов A =< {a,b}, {q,p}, q, {p}, ΦA> и B =< {a,b}, {1, 2, 3}, 1, {1, 2}, ΦB>, [Большая Картинка] распознающих языки LA и LB, соответственно. Какой из следующих автоматов является произведением A × B и какой язык он реализует? C = <{a,b}, { (q, 1), (q,2), (q,3), (p, 1), (p,2), (p,3)}, (q,0), F={(q, 1), (q, 2)}, ΦC >, D = <{a,b}, { (q, 1), (q,2), (q,3), (p, 1), (p,2) , (p,3)}, (q,0), F={(p,3)}, ΦD >, [Большая Картинка]
• # Пусть регулярное выражение b*(a+b)* определяет некоторый язык над алфавитом S={a, b} . Другим регулярным выражением для этого языка может быть:
• # Пусть машина Тьюринга M имеет алфавит ленты Σ={ ∧, 0, 1}, алфавит состояний Q= {q, p, r, !}, начальное состояние q, заключительное состояние ! и программу Ф: \begin{array}{lll} q\ 0 \rightarrow q\ 0\ П & p\ 0 \rightarrow p\ 1\ Л & r\ 0 \rightarrow r\ 0\ Л q\ 1 \rightarrow q\ 1\ П & p\ 1 \rightarrow r\ 0\ Л & r\ 1 \rightarrow r\ 1\ Л q \wedge \rightarrow p\ \wedge Л & p \wedge \rightarrow ! \wedge П & r \wedge \rightarrow ! \wedge П \end{array} В какую из следующих заключительных конфигураций она перейдет, начав работу в конфигурации q 1010 ?