Введение в схемы, автоматы и алгоритмы

<<- Назад к вопросам

Пусть задана линейная программа P со входными переменными X1, X2, X3:
Y = ¬X1;
Z = ¬X2;
U = ¬X3;
Y = Y ∧ X2;
W = X2 ∧ X3;
Y = Y ∧ U;
Y = W ∨ Y ;
Z = Z ∨ Y.
Постройте логическую схему S_P со входами X1, X2, X3 и функциональными вершинами, соответствующими командам P, вычисляющую ту же функцию, что и P в выходной переменной Z. Чему равна ее глубина?

(Отметьте один правильный вариант ответа.)

Варианты ответа

5(Верный ответ)

Похожие вопросы

Пусть задана линейная программа P со входными переменными X1, X2, X3:

Y = ¬X1;

Z = ¬X2;

U = ¬X3;

V = X1 ∧ X2;

Z = Y ∧ Z;

W= Y ∧ X2;

Z = Z ∧ W ;

V = V ∧ U ;

Z = Z ∨ V.

Постройте логическую схему S_P со входами X1, X2, X3 и функциональными вершинами, соответствующими командам P, вычисляющую ту же функцию, что и P в выходной переменной Z. Чему равна ее глубина?

Пусть задана линейная программа P со входными переменными X1, X2, X3:

Y = X1 ∨ X2;

Z = X1 ∨ X3;

U = ¬X3;

Y = Y ∧ Z;

W = X2 ∨ X3;

U = X2 ∨ U;

Z = W ∨ Y ;

Z = U ∧ Y.

В доказательстве теоремы 20.2 для построения м.Т M_П, моделирующей работу структурированной программы П с переменными x₁, … , x_m, используются м.Т. M^ij (1 ≤ i, j ≤ m), которые реализуют присваивание x_i := x_j, т.е. переписывают содержимое j-го этажа ленты на i-ый. Пусть m=4, i=3, j=1. Пусть Σ = { < a1, a2, a3, a4> | ai ∈ {∧, |}, i=1,2,3,4 } – алфавит ленты, а Q={ q, s, p },– множество состояний M⁴³, в котором q - начальное, а p – заключительное состояние.Какие из следующих программ могут быть использованы в качестве программы для M⁴³ ?(В текстах программ a,b,c,d – это произвольные символы из алфавита{∧, |})

P1: q <a, b, |, d > → q < a, b , |, | > П , s < a, ,b | , | > → s < a, b, | , | > Л , q < ∧, b, ∧, d> → s < ∧ , b, ∧, d > Л , s < ∧, ∧, ∧, ∧> → p < ∧, ∧, ∧, ∧> П ,

P3: : q <a, b, |, d > → q < a, b , |, | > П , s < a, ,b | , | > → s < a, b, | , | > Л , q <a, b, ∧, | > → q < a, b, ∧, ∧ > П , s < ∧, ∧, ∧, ∧> → p < ∧, ∧, ∧, ∧> П. q < ∧, b, ∧, d> → s < ∧ , b, ∧, d > Л ,

В доказательстве теоремы 20.2 для построения м.Т M_П, моделирующей работу структурированной программы П с переменными x₁, … , x_m, используются м.Т. M^ij (1 ≤ i, j ≤ m), которые реализуют присваивание x_i := x_j, т.е. переписывают содержимое j-го этажа ленты на i-ый. Пусть m=4, i=2, j=4. Пусть Σ = { < a1, a2, a3, a4> | ai ∈ {∧, |}, i=1,2,3,4 } – алфавит ленты, а Q={ q, s, p },– множество состояний M²⁴, в котором q - начальное, а p – заключительное состояние.Какие из следующих программ могут быть использованы в качестве программы для M²⁴ ?(В текстах программ a,b,c,d – это произвольные символы из алфавита{∧, |})

P1: q <a, b, c, |> → q <a, | , c, | > П , s <a, | , c, | > → s <a, | , c, | > Л , q <a, |, c, ∧> → q <a, ∧ , c, ∧> П , s <∧, ∧, ∧, ∧> → p <∧, ∧ , ∧, ∧> П. q <a, ∧, c, ∧> → s <a, ∧ , c, ∧> Л ,

P2: q <a, |, c, d> → q <a, | , c, | > П , s <a, | , c, | > → s <a, | , c, | > Л , q <a, ∧, c, |> → q <a, ∧ , c, ∧> П , s <a, ∧, c, ∧> → p <a, ∧ , c, ∧> П. q <a, ∧, c, ∧> → s <a, ∧ , c, ∧> Л ,

P3: q <a, b, c, |> → q <a, | , c, | > П , s <a, | , c, | > → s <a, | , c, | > Л , q <a, b, c, ∧> → s <a, ∧ , c, ∧> Л , s <a, ∧, c, ∧> → p <a, ∧ , c, ∧> П.

В доказательстве теоремы 20.2 для построения м.Т M_П, моделирующей работу структурированной программы П с переменными x₁, … , x_m, используются м.Т. M^ij (1 ≤ i, j ≤ m), которые реализуют присваивание x_i := x_j, т.е. переписывают содержимое j-го этажа ленты на i-ый. Пусть m=4, i=3, j=1. Пусть Σ = { < a1, a2, a3, a4> | ai ∈ {∧, |}, i=1,2,3,4 } – алфавит ленты, а Q={ q, s, p },– множество состояний M³¹, в котором q - начальное, а p – заключительное состояние.Какие из следующих программ могут быть использованы в качестве программы для M³¹ ?(В текстах программ a,b,c,d – это произвольные символы из алфавита{∧, |})

P1: q <|, b, c, d > → q < |, b , |, d > П , s < | , b, |, d > → s < | , b, |, d > Л , q <∧, b, |, d > → q < ∧, b, ∧, d > П , s < ∧, ∧, ∧, ∧> → p < ∧, ∧, ∧, ∧> П. q < ∧, b, ∧, d> → s < ∧ , b, ∧, d > Л ,

P3: : q <|, b, c, d > → q < |, b , |, d > П , s < | , b, |, d > → s < | , b, |, d > Л , q < ∧, b, ∧, d> → s < ∧ , b, ∧, d > Л , s < ∧, ∧, ∧, ∧> → p < ∧, ∧, ∧, ∧> П.

Пусть П_× - это программа, которая вычисляет функцию Ф_× (x,y) = x·y в переменной x, используя две рабочих переменных z и i Какие из следующих структурированных программ П1, П2, П3 вычисляют в переменной x целую часть частного [ x/y] (пусть при y=0 результат равен 0)?

Пусть П_× - это программа, которая вычисляет функцию Ф_× (x,y) = x·y в переменной x, используя две рабочих переменных z и i Какие из следующих структурированных программ П1, П2, П3 вычисляют в переменной x двоичный логарифм от x, т.е. функцию [ log₂( x)]?

Пусть П_× - это программа, которая вычисляет функцию Ф_× (x,y) = x·y в переменной x, используя две рабочих переменных z и i Какие из следующих структурированных программ П1, П2, П3 вычисляют в переменной x квадратный корень из x, т.е. функцию [ x ^1/2]?

В доказательстве теоремы 10.1 для построения м.Т., реализующей оператор примитивной рекурсии F(x,y) = R( g¹, f³), требовалась м.Т. M₁, которая переводит конфигурацию вида |^x* |^y в конфигурацию |^y * |^x* ∧ *|^g(x) , используя м.Т. M_g, вычисляющую функцию g(x).Какие из следующих программ м.Т. выполняют требуемую работу, т.е. могут быть использованы в качестве программы для M₁ ?

P1 = Коп_#; par_# (par_* (Чист, Пуст); Зам(*,∧ ) , par_* (Пуст ,Чист); Зам(*,∧ ) ); par_# (Пуст, Коп_* ); par_* (Пуст, +1; +1; Зам(|,∧ ); Зам(|,* )); par_* (Пуст, Пуст, M_g); Зам( #,* )

P2 = Коп_#; par_# (par_* (Чист, Пуст); Зам(*,∧ ) , par_* (Пуст ,Чист); Зам(*,∧ ) ); par_# (Пуст, Коп_# ); par_# (Пуст, Пуст, M_g ; +1; +1; Зам(|,∧ ); Зам(|,* )); Зам( #,* ); Зам( #,* )

P3 = Коп_*; par_* (Чист, Пуст, Пуст ,Чист); Зам(*,∧ ); Зам(*,# ); Зам(*,∧ ); par_# (Пуст, M_g ; +1; +1; Зам(|,∧ ); Зам(|,* )); Зам( #,* )

В этих определениях участвуют следующие простые машины Тьюринга:

Коп_a – копирует вход после разделительного символа a : w ⇐ w a w;

Зам(a, b) – заменяет первое слева вхождение символа a на b: w₁a w₂ ⇐ w₁ b w₂( a ∉ w₁ );

Пуст – не изменяет аргумент: w ⇐ w ;

Чист – стирает аргумент: w ⇐ ∧ ;

+1 – прибавляет 1 к аргументу: |^x ⇐ |^x+1

Предположим, что в некоторой конфигурации машины Тьюринга M на ленте записано слово w в алфавите Σ, не содержащем символов ∧ и *, но головка "заблудилась" – она наблюдает символ ∧ и не знает левее или правее слова w находится. Какие из следующих программ помогут найти начало слова w, т.е. любую конфигурацию вида q ∧^k w или w∧^kq ∧ (k > 0) переведут в конфигурацию q'w ?(В текстах программ a – это произвольный символ из Σ, используемые состояния: q, q', l, r, l₁, r₁ , l₂, r₂, l₃, r₃, l₄)

P1: q ∧ → l₁ * Л, l₁∧→ r * П, l₁a→ l₂a П, l₂a→ l₂ a Л, l₂∧→ q'∧ П, r∧ → r ∧ П, r *→ r₁ ∧ П, r₁ ∧→ l * Л, l ∧→ l ∧ Л, l *→ l₁ ∧ Л, r₁ a→ r₂a Л, r₂∧→ r₂∧ Л, r₂*→ r₃∧ П, r₃∧→ r₃∧ П, r₃a→ q'a Н.

P2: q ∧ → l₁ * Л, l₁∧→ r * П, l₁a→ l₂a П, l₂∧→ l₂∧ П, l₂*→ l₃∧ Л, l₃∧→ l₃∧ Л, l₃a→ q'a Н,r∧ → r ∧ П, r *→ r₁ ∧ П, r₁ ∧→ l * Л, l ∧→ l ∧ Л, l *→ l₁ ∧ Л,r₁ a→ r₂a Л, r₂∧→ r₂∧ Л, r₂*→ r₃∧ П, r₃∧→ r₃∧ П, r₃a→ q'a Н.

P3: q ∧ → l₁ * Л, l₁∧→ r * П, l₁a→ l₂a П, l₂∧→ l₂∧ П, l₂*→ l₃∧ Л, l₃∧→ l₃∧ Л, l₃a→ l₄ a Л,l₄a→ l₄ a Л, l₄∧→ q'∧ П, r∧ → r ∧ П, r *→ r₁ ∧ П, r₁ ∧→ l * Л, l ∧→ l ∧ Л, l *→ l₁ ∧ Л,r₁ a→ r₂a Л, r₂∧→ r₂∧ Л, r₂*→ r₃∧ П, r₃∧→ r₃∧ П, r₃a→ q'a Н.