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

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

Чему равна глубина схемы Sodd , реализующей функцию
odd(X1, X2, …,Xn) = X1 + X2 + … Xn ?


Пусть задана логическая схема S=(V, E) :
V= {a (X), b(Y), c(Z), d(V), e(?), f(¬),g(¬),h(?), i(?), k(¬), m(?) } (после имени вершины в скобках указана ее метка — переменная или булева функция),
E= { (a, e), (b, f), (c, g), (d, e), (d, i), (e, k), (f, h), (g,, h), (h, i),(i, m), (k, m) }.
Какие из следующих линейных программ вычисляют в переменной Z ту же функцию F(X,Y,Z,V), что и схема S в вершине m?

P1:                        P2:                             P3:
V = X ? V;                 f = ¬Y;                         Y = ¬Y;
V = ¬V;                    g = ¬Z;                         Z = ¬Z;
Y = ¬Y;                    e = X ? V;                      Z = Y ?Z;
Z = ¬Z;                    k = ¬e;                         Z = Z ?V;
Y = Y ? Z;                 h = f ? g;                      V = X ? V;
Z = Y ? V;                 i = h ? V;                      V = ¬V;
Z = V ? Z .                Z = h ? k.                      Z = Z ? V.


Какую булеву функцию реализует эта логическая схема в вершине a ?


Чему равна глубина схемы S3, реализующей функцию сложения трехбитовых чисел?


Пусть задана логическая схема S=(V, E) :
V= {a (X1), b(X2), c(X3), d(¬),e(¬), f(?),g(?),h(?), i(?), k(?) } (после имени вершины в скобках указана ее метка — переменная или булева функция),
E= { (a, d), (a, g), (b, e), (b, f), (c, f), (c, h), (d, h), (e, g), (f,k), (g, i), (i, k) }.
Какую булеву функцию реализует схема S=(V, E) в вершине k?
(В ответах функции заданы последовательностями 8 нулей и единиц — их значениями на лексикографически упорядоченных наборах значений аргументов X1, X2 и X3)


Пусть задана линейная программа 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.
  • Постройте логическую схему SP со входами X1, X2, X3 и функциональными вершинами, соответствующими командам P, вычисляющую ту же функцию, что и P в выходной переменной Z. Чему равна ее глубина?


    Пусть задана логическая схема S=(V, E) :
    V= {a (X1), b(X2), c(X3), d(¬),e(¬), f(¬),g(?),h(?), i(?), k(?) } (после имени вершины в скобках указана ее метка — переменная или булева функция),
    E= { (a, d), (a, g), (b, e), (c, f), (c, g), (d, i), (e, h), (f,h), (g,k), (i, k) }.
    Какую булеву функцию реализует схема S=(V, E) в вершине k?
    (В ответах функции заданы последовательностями 8 нулей и единиц — их значениями на лексикографически упорядоченных наборах значений аргументов X1, X2 и X3)


    Какие из следующих схем реализуют в вершине a функцию, заданную формулой
    A = ((a ? ¬b) ? ¬b) ? ¬ (b? c) ?



    Пусть задана линейная программа 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.
  • Постройте логическую схему SP со входами X1, X2, X3 и функциональными вершинами, соответствующими командам P, вычисляющую ту же функцию, что и P в выходной переменной Z. Чему равна ее глубина?


    Какие из следующих схем реализуют в вершине a функцию, заданную формулой
    A = ¬ (a ? ¬b) ? ((b? c) ? (a ? ¬b)) ?


    Чему равна глубина схемы S1, реализующей функцию сложения однобитовых чисел?



    Какая из следующих формул задает булеву функцию, которую реализует эта диаграмма?


    Какие из следующих УБДР являются сокращенными?


    Пусть задана УБДР D=(V,E): V={v1 (x), v2(y), v3(y), v4(z), v5(z), v6(z), v7(w), v8(w), v9(w), 0, 1} (в скобках после имени вершины указана переменная, которой она помечена),
    E = { (v1, v2; 1), (v1, v3; 0), (v2, v4; 1), (v2, v5; 0), (v3, v4; 1), (v3, v6; 0), (v4, v7; 1),
    (v4, v8; 0), (v5, v8; 1), (v5, v9; 0), (v6, v8; 1), (v6, v9; 0), (v7, 0; 1), (v7, 1; 0), (v8, 0; 0),
    (v8, 1; 1), (v9, 0; 0), (v9, 1; 1) }
    ( для каждого ребра третий параметр после ; — его метка 0 или 1).
    Постройте по D эквивалентную ей сокращенную УБДР и укажите ее сложность.



    Какую булеву функцию реализует эта диаграмма?
    (В ответах функции заданы последовательностями 8 нулей и единиц — их значениями на лексикографически упорядоченных наборах значений аргументов x1, x2 и x3)


    Пусть задана УБДР D=(V,E):
    V={v1 (x), v2(y), v3(y), v4(z), v5(z), v6(z), v7(w), v8(w), , 0, 1} (в скобках после имени вершины указана переменная, которой она помечена),
    E = { (v1, v2; 1), (v1, v3; 0), (v2, v4; 0), (v2, v5; 1), (v3, v5; 1), (v3, v6; 0), (v4, v7; 0),
    (v4, v8; 1), (v5, v7; 0), (v5, v8; 1), (v6, v8; 1), (v6, v7; 0), (v7, 0; 1), (v7, 1; 0), (v8, 0; 1), (v8, 1; 0)}
    ( для каждого ребра третий параметр после ; — его метка 0 или 1).
    Постройте по D эквивалентную ей сокращенную УБДР и укажите ее сложность.


    Пороговая функция Tn,k от n переменных с порогом k равна 1, если во входном наборе (x1, … , xn) имеется не менее k единиц. Постройте минимальную УБДР для пороговой функции T5,3 относительно стандартного порядка переменных: x1 < x2 < x3< x4< x5. Какова сложность этой схемы?



    Какую булеву функцию реализует эта диаграмма?
    (В ответах функции заданы последовательностями 8 нулей и единиц — их значениями на лексикографически упорядоченных наборах значений аргументов x1, x2 и x3)


    Постройте минимальные УБДР для функции
    f(x1, x2, x3, x4)= (x1 ? x2) + ( x3 ? x4)
    относительно двух упорядочений переменных:

  • a) x1 < x2 < x3 < x4 и
  • b) x1 < x3 < x2 < x4.
  • Определите сложности этих двух схем.



    Какую булеву функцию реализует эта диаграмма?
    (В ответах функции заданы последовательностями 8 нулей и единиц — их значениями на лексикографически упорядоченных наборах значений аргументов x1, x2 и x3)


    Постройте минимальные УБДР для функции
    f(x1, x2, x3, x4)= (x1 ? x2) ? ( x3 ? x4)
    относительно двух упорядочений переменных:

  • a) x1 < x2 < x3 < x4 и
  • b) x1 < x3 < x2 < x4.
  • Определите сложности этих двух схем.


    Какие из следующих УБДР являются сокращенными?



    Пороговая функция Tn,k от n переменных с порогом k равна 1, если во входном наборе (x1, … , xn) имеется не менее k единиц. Постройте минимальную УБДР для пороговой функции T5,2 относительно стандартного порядка переменных: x1 < x2 < x3< x4< x5. Какова сложность этой схемы?



    Какую булеву функцию реализует эта диаграмма?
    (В ответах функции заданы последовательностями 8 нулей и единиц — их значениями на лексикографически упорядоченных наборах значений аргументов x1, x2 и x3)


    Постройте минимальные УБДР для функции
    f(x1, x2, x3, x4)= (x1 ? x2) +( x3 ? x4)
    относительно двух упорядочений переменных:

  • a) x1 < x2 < x3 < x4 и
  • b) x1 < x3 < x2 < x4.
  • Определите сложности этих двух схем.


    Пороговая функция Tn,k от n переменных с порогом k равна 1, если во входном наборе (x1, … , xn) имеется не менее k единиц. Постройте минимальную УБДР для пороговой функции T4,2 относительно стандартного порядка переменных: x1 < x2 < x3< x4< x5. Какова сложность этой схемы?



    Какую булеву функцию реализует эта диаграмма?
    (В ответах функции заданы последовательностями 8 нулей и единиц — их значениями на лексикографически упорядоченных наборах значений аргументов x1, x2 и x3)


    Пусть задана УБДР D=(V,E): V={v1(x), v2(y), v3(y), v4(z), v5(z), v6(z), v7(w), v8(w), , 0, 1} (в скобках после имени вершины указана переменная, которой она помечена), E = { (v1, v2; 1), (v1, v3; 0), (v2, v4; 0), (v2, v5; 1), (v3, v5; 1), (v3, v6; 0), (v4, v7; 0),
    (v4, v8; 1), (v5, v7; 0), (v5, v8; 1), (v6, v8; 1), (v6, v7; 0), (v7, 0; 1), (v7, 1; 0), (v8, 0; 0), (v8, 1; 1)}
    ( для каждого ребра третий параметр после ; — его метка 0 или 1).
    Постройте по D эквивалентную ей сокращенную УБДР и укажите ее сложность.


    Ниже приведен конечный автомат — распознаватель
    A= <? ={a, b}, Q ={ 0, 1, 2, 3, 4, 5 }, 0, F={ 3, 4}, ?>,
    где

    Какие из следующих трех слов распознаются автоматом A?
    W= aaabbabab, V= babbbabba, U= ababaaab


    На следующем рисунке представлены диаграммы двух конечных автоматов 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,1), (p,2)}, ?D >,


    Пусть задан недетерминированный конечный автомат
    (без пустых переходов)
    M = < {0, 1}, {q, p, s}, q, F={p}, ?> с программой
    ?: q 0 >? q, q 1 >? s, q 1>? p, p 0 >? q, p 0 >? p, s 0 >? q, s 1 >? p
    Какие из следующих трех ДКА эквивалентны M?

    M1 = < {0, 1}, {q, p, s, ps, qs, pq, qps, ?}, q, F1={p, ps, pq, pqs }, ?1> с программой ?1:
    q 0 >? q, q 1 >? ps, p 0 >? pq, p 1 >? ?, s 0 >? q, s 1 >? pq, ps 0 >? pq, ps 1 >? p, pq 0 >? pq, pq 1 >? p, qs 0 >? q, qs 1 >?pq, pqs 0 >? pq, pqs 1 >? ps, ? 0 >??, ? 1 >??

    M2 = < {0, 1}, { q, p, s, ps, qs, pq, qps, ?}, q, F2={ p, ps, pq, pqs }, ?2> с программой ?2:
    q 0 >? q, q 1 >? ps, p 0 >? pq, p 1 >? q, s 0 >? q, s 1 >? pq, ps 0 >? pq, ps 1 >? p, pq 0 >? pq, pq 1 >? ps, qs 0 >? q, qs 1 >?pq, pqs 0 >? pq, pqs 1 >? ps, ? 0 >??, ? 1 >??

    M3 = < {0, 1}, {q, p, ps, pq, ? }, q, F3={ ps, pq, p }, ?3> с программой ?3:
    q 0 >? q, q 1 >? ps, ps 0 >? pq, ps 1 >? p, pq 0 >? pq, pq 1 >? ps, p 0 >? pq, p 1 >? ?, ? 0 >??, ? 1 >??


    Ниже приведена диаграмма конечного автомата
    A= <? ={a, b}, Q ={ q, p, r, s }, q, F={s}, ?>,

    Какой из следующих языков распознает автомат A ?


    Ниже приведен конечный автомат — распознаватель
    A= <? ={a, b}, Q ={ 0, 1, 2, 3, 4, 5 }, 0, F={ 3, 4}, ?>,
    где

    Какие из следующих трех слов распознаются автоматом A?
    W= aaabaababaab, V= babbbaabba, U= ababaaabba


    Какие из следующих трех конечных автоматов
    Ai = < {a,b}, {0, 1, 2, 3, 4}, 0, F={1}, ?i> (i= 1, 2, 3) распознают язык L, состоящий из всех слов, которые заканчиваются на b и содержат число букв a , кратное 3 ?


    На следующем рисунке представлены диаграммы двух конечных автоматов 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 >,


    Пусть задан конечный автомат — преобразователь
    A = <?X ={0, 1} ?Y= { А, Р, Т}, Q ={ 0, 1, 2, 3 }, 0, ?, ?>, где

    Какое входное слово автомат А перерабатывает в выходное слово АРАРАТ?


    Следующий конечный автомат — преобразователь
    MINUS= <?X ={0, 1} ?Y= { 0, 1}, Q ={ 0, 1, 2, 3 }, 0, ?, ?>,
    где

    вычитает из входного двоичного числа x некоторую константу c и выдает при c ? x выходное двоичное число y = x –c Чему равна эта константа c?


    Какие из следующих трех конечных автоматов
    Ai = < {a,b}, {0, 1, 2, 3}, 0, F={1}, ?i> (i= 1, 2, 3) распознают язык L, состоящий из всех слов, которые начинаются на a и содержат четное число букв b ?


    Ниже приведен конечный автомат — распознаватель
    A= <? ={a, b}, Q ={ 0, 1, 2, 3, 4, 5 }, 0, F={ 3, 4}, ?>,
    где

    Какие из следующих трех слов распознаются автоматом A?
    W= aaabaabab, V= abababaab, U= bbabbbababa


    Ниже приведена диаграмма конечного автомата
    A= <? ={a, b}, Q ={ q, p, r, s }, q, F={s}, ?>,

    Какой из следующих языков распознает автомат A ?


    На следующем рисунке представлены диаграммы двух конечных автоматов 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 >,


    Следующий конечный автомат — преобразователь
    MINUS= <?X ={0, 1} ?Y= { 0, 1}, Q ={ 0, 1, 2 }, 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={(p,3)}, ?C >,

    D = <{a,b}, { (q, 1), (q,2), (q,3), (p, 1), (p,2) , (p,3)}, (q,0), F={(p,1), (p,2)}, ?D >,


    Следующий конечный автомат — преобразователь
    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={(p,3)}, ?C >,

    D = <{a,b}, { (q, 1), (q,2), (q,3), (p, 1), (p,2) , (p,3)}, (q,0), F={(p,1), (p,2)}, ?D >,


    Пусть задан конечный автомат — преобразователь
    A = <?X ={0, 1} ?Y= { А, Р, Т}, Q ={ 0, 1, 2, 3 }, 0, ?, ?>,
    где

    Какое входное слово автомат А перерабатывает в выходное слово ТАРАРА?


    Ниже приведена диаграмма конечного автомата
    A= <? ={a, b}, Q ={ q, p, r, s }, q, F={s}, ?>,

    Какой из следующих языков распознает автомат A ?


    На следующем рисунке представлены диаграммы двух конечных автоматов 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,1), (p,2)}, ?D >,


    Пусть задан конечный автомат — преобразователь
    A = <?X ={0, 1} ?Y= { А, Р, Т}, Q ={ 0, 1, 2, 3 }, 0, ?, ?>,
    где

    Какое входное слово автомат А перерабатывает в выходное слово ТАРТАР?


    На следующем рисунке представлены диаграммы двух конечных автоматов 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 >,


    Пусть задан недетерминированный конечный автомат
    (без пустых переходов)
    M = < {0, 1}, {q, p, s}, q, F={p}, ?> с программой
    ?: q 0 >? p, q 0 >? s, p 0 >? q, p 0 >? s, p 1 >? p, s 1 >? p
    Какие из следующих трех ДКА эквивалентны M?

    M1 = < {0, 1}, {q, p, ps, qs}, q, F1={p, ps}, ?1> с программой
    ?1: q 0 >? ps, q 1 >? p, p 0 >? qs, p 1 >? p, ps 0 >? qs, ps 1 >? p, qs 0 >? ps, qs 1 >? p

    M2 = < {0, 1}, {q, p, s, ps, qs, pq, qps, ?}, q, F2={p, ps, pq, qps}, ?2> с программой
    ?2: q 0 >? ps, q 1 >? p, p 0 >? qs, p 1 >? p, s 0>? ?, s 1>? p, ps 0 >? qs, ps 1 >? p, qs 0 >? ps, qs 1 >? p, qp 0 >? ps, qp 1 >? p, qps 0 >? qps, qps 1 >? p, ? 0 >??, ? 1 >??.

    M3 = < {0, 1}, { q, p, s, ps, qs, pq, qps, ?}, q, F3={ p, ps, pq, qps }, ?3> с программой
    ?3: q 0 >? ps, q 1 >? p, p 0 >? qs, p 1 >? p, s 1>? p, ps 0 >? qs, ps 1 >? p, qs 0 >? qps,
    qs 1 >?qps, qp 0 >? ps, qp 1 >? p, qps 0 >? qps, qps 1 >? p. ? 0 >??, ? 1 >? ?


    На следующем рисунке представлены диаграммы двух конечных автоматов 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 >,


    На следующем рисунке представлены диаграммы двух конечных автоматов 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,1), (p,2)}, ?D >,


    Пусть задан недетерминированный конечный автомат
    (без пустых переходов)
    M = < {0, 1}, {q, p, s}, q, F={p}, ?> с программой
    ?: q 0 >? p, q 0 >? s, q 1>? q, p 0 >? q, p 0 >? p, s 1 >? q, s 1 >? p
    Какие из следующих трех ДКА эквивалентны M?

    M1 = < {0, 1}, {q, ps, pq, pqs}, q, F1={ ps, pq, pqs }, ?1> с программой ?1:
    q 0 >? ps, q 1 >? q, ps 0 >? pq, ps 1 >? pq, pq 0 >? pqs, pq 1 >? q, pqs 0 >? pqs, pqs 1 >? pq

    M2 = < {0, 1}, {q, p, s, ps, qs, pq, qps, ?}, q, F2={p, ps, pq, pqs }, ?2> с программой ?2:
    q 0 >? ps, q 1 >? q, p 0 >? pq, p 1 >? q, ps 0 >? qs, ps 1 >? pq, pq 0 >? pqs, pq 1 >? q,
    qs 0 >? ps, qs 1 >?q, pqs 0 >? pqs, pqs 1 >? pq, ? 0 >??, ? 1 >??

    M3 = < {0, 1}, { q, p, s, ps, qs, pq, qps, ?}, q, F3={ p, ps, pq, pqs }, ?3> с программой ?3:
    q 0 >? ps, q 1 >? q, p 0 >? pq, p 1 >? q, s 0 >??, s 1 >?pq, ps 0 >? pq, ps 1 >? pq, pq 0 >? pqs, pq 1 >? q, qs 0 >? ps, qs 1 >?q, pqs 0 >? pqs, pqs 1 >? pq, ? 0 >??, ? 1 >??


    Какие из следующих трех конечных автоматов
    Ai = < {a,b}, {0, 1, 2, 3, 4}, 0, F={1}, ?i> (i= 1, 2, 3) распознают язык L, состоящий из всех слов, которые начинаются на b и содержат число букв a , кратное 3 ?


    На следующем рисунке представлены диаграммы двух конечных автоматов 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={(p,3)}, ?C >,

    D = <{a,b}, { (q, 1), (q,2), (q,3), (p, 1), (p,2) , (p,3)}, (q,0), F={(p,1), (p,2)}, ?D >,


    На следующем рисунке представлены диаграммы двух конечных автоматов 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,1), (p,2)}, ?D >,


    На следующем рисунке представлены диаграммы двух конечных автоматов 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 >,


    На следующем рисунке представлены диаграммы двух конечных автоматов 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={(p,3)}, ?C >,

    D = <{a,b}, { (q, 1), (q,2), (q,3), (p, 1), (p,2) , (p,3)}, (q,0), F={(p,1), (p,2)}, ?D >,


    На следующем рисунке представлены диаграммы двух конечных автоматов 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,1), (p,2)}, ?D >,


    На следующем рисунке представлены диаграммы двух конечных автоматов 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 >,


    На следующем рисунке представлены диаграммы двух конечных автоматов 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={(p,3)}, ?C >,

    D = <{a,b}, { (q, 1), (q,2), (q,3), (p, 1), (p,2) , (p,3)}, (q,0), F={(p,1), (p,2)}, ?D >,


    На следующем рисунке представлены диаграммы двух конечных автоматов 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={(p,3)}, ?C >,

    D = <{a,b}, { (q, 1), (q,2), (q,3), (p, 1), (p,2) , (p,3)}, (q,0), F={(p,1), (p,2)}, ?D >,


    На следующем рисунке представлены диаграммы двух конечных автоматов 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,1), (p,2)}, ?D >,


    На следующем рисунке представлены диаграммы двух конечных автоматов 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 >,


    На следующем рисунке представлены диаграммы двух конечных автоматов 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 >,


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

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

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

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

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



    Какое из следующих регулярных выражений задает все слова из 0-ей и 1-иц, в которых есть по крайней мере две подряд идущие 1-цы ?


    Пусть регулярное выражение b*(a+b)* определяет некоторый язык над алфавитом S={a, b} . Другим регулярным выражением для этого языка может быть:


    Какой язык L является конкатенацией двух языков:
    L1= {a, ab, abba} и L2= { ?, a, b, ba}?


    Заданы два НКА:

    A =< {a, b}, {0, 1, 2, 3}, 0, {2}, ?A > с программой
    ?A: 0 a >? 1, 0 b >? 3, 1 a >? 3 1 b >? 2, 2 a >? 3, 2 b >? 2, 3 a >? 3, 3b >? 3 и

    B =< {a, b}, {q0, q1, q2}, q0, {q2}, ?B > с программой ?B: q0 a >? q0, q0 b >? q1,
    q1 a >? q1, q1 a >? q2

    Какие из следующих трех НКА С1 , С2 , С3 распознают конкатенацию LA? LB языков, распознаваемых автоматами A и B?
    С1 = < {a,b}, {0, 1, 2, 3, q0, q1, q2}, 0, F1={ q2},
    ?1>, С2 = < {a,b}, {0, 1, 2, 3, q0, q1, q2}, 0, F2={ q2}, ?2>, С3 = < {a,b}, {0, 1, 2, 3, q1, q2}, 0, F3={ q2}, ?3>, где программы заданы в следующих таблицах (? означает отсутствие соответствующего перехода).



    Какой язык L является конкатенацией двух языков:
    L1= {?, b, ab, abba} и L2= { a, b, ba}?


    Пусть регулярное выражение b(ab)* определяет некоторый язык над алфавитом S={a, b} . Другим регулярным выражением для этого языка может быть:


    Какой язык L является конкатенацией двух языков:
    L1= {?, b, ab, ba} и L2= {?, a, b, ba}?


    Пусть S={aa, ab, ba, bb} Какая из следующих фраз описывает итерацию S* этого языка?


    Какие из следующих трех автоматов С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>,

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



    Пусть задан ДКА A =< {a, b}, {Q, P, R, S}, Q, F= {R}, ?A > с программой ?A: { Q a >? P, Q b >? Q, P b >? P, P a >? R, R a >? Q, R b >? S, S a >? S, S b >? S} и гомоморфизм h: {0, 1, 2}* >? {a, b}*: h(0) = aba, h(1) = aa, h(2) = ? Какие из следующих трех автоматов С1, С2, С3 распознают гомоморфный прообраз h-1(LA)?

    С1 = < {0, 1}, { Q, P, R, S }, 0, F1={ R }, ?1>,

    С2 = < {0, 1}, { Q, P, R, S }, 0, F2={ R }, ?2>,

    С3 = < {0, 1}, { Q, P, R, S }, 0, F3={ R }, ?3>,

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



    Используя теорему о разрастании, установите, какие из следующих трех языков в алфавите {a, b} не являются автоматными.

    L1 = { a2bna2 | n > 0 },

    L2 = { ww | w = a2bna2 , n > 0 },

    L3 = { wv | w = a2bna2 , v = b2amb2 для произвольных n,m > 0 }.


    Пусть язык L в алфавите {a, b, c}, состоит из всех слов, которые начинаются на aa и содержат подслово bb Какая из следующих фраз определяет язык h(L), являющийся образом L при гомоморфизме h: {a, b, c}* >? {0, 1}* где h(a) = 01, h(b) = 11, h(c) = ? ?

    Пусть задан ДКА A =< {a, b, c}, {0, 1, 2}, 0, F= {2}, ?A > с программой ?A: { 0 a >? 1, 0 b >? 0, 0 c >? 1, 1 a >? 2, 1 b >? 1, 1 c >? 1, 2 a >? 2, 2 b >? 2, 2 c >? 1} и гомоморфизм h: {a, b, c}* >? {0, 1}*:
    h(a) = 01, h(b) = 1, h(c) = ?

    Какие из следующих трех автоматов С1, С2, С3 распознают гомоморфный образ h(LA)?

    С1 = < {0, 1}, {0, 1, 2, q1, q2, q3}, 0, F1={2}, ?1>,

    С2 = < {0, 1}, {0, 1, 2, q1, q2 }, 0, F2={2}, ?2>,

    С3 = < {0, 1}, {0, 2, (q1, q2), (0,1), (1, 2), !}, 0, F3={2, (1,2)}, ?3>,

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



    Пусть язык L в алфавите {a, b, c}, состоит из всех слов, в которых количество букв b превосходит количество букв a не менее чем на 2. Предположим, что L автоматный язык и что n – это константа, которая существует для него по утверждению теоремы о разрастании. Какое из следующих «специальных» слов позволяет опровергнуть это предположение, т.е. для какого из них не выполнено утверждение 3 теоремы о разрастании?

    Пусть язык L в алфавите {a, b, c}, состоит из всех слов, в которых количество букв b превосходит количество букв a не менее чем на 3. Предположим, что L автоматный язык и что n – это константа, которая существует для него по утверждению теоремы о разрастании. Какое из следующих «специальных» слов позволяет опровергнуть это предположение, т.е. для какого из них не выполнено утверждение 3 теоремы о разрастании?

    Пусть язык L в алфавите {a, b, c}, состоит из всех слов, которые заканчиваются на bcc и содержат подслово aca Какая из следующих фраз определяет язык h(L), являющийся образом L при гомоморфизме h: {a, b, c}* >? {0, 1}* где
    h(a) = 00, h(b) = 10, h(c) = ? ?

    Пусть задан ДКА A =< {a, b, c}, {0, 1, 2}, 0, F= {2}, ?A > с программой ?A: { 0 a >? 0, 0 b >? 1, 0 c >? 1, 1 a >? 1, 1 b >? 2, 1 c >? 1, 2 a >? 2, 2 b >? 2, 2 c >? 1} и гомоморфизм h: {a, b, c}* >? {0, 1}*:
    h(a) = 1, h(b) = 01, h(c) = ?.
    Какие из следующих трех автоматов С1, С2, С3 распознают гомоморфный образ h(LA)?

    С1 = < {0, 1}, {0, 1, 2, q1, q2, q3}, 0, F1={2}, ?1>,

    С2 = < {0, 1}, {0, 1, 2, q1, q2 }, 0, F2={2}, ?2>,

    С3 = < {0, 1}, {0, 2, (q1, q2), (0,1), (1, 2), !}, 0, F3={2, (1,2)}, ?3>,

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



    Пусть структурированная программа

    P:  
    x:= y+1;  v:= u+1;  y := z+1; 
    пока  x < v  делай
       если  x < y   то
                               x := y+1
                        иначе  y := x +1
       конец 
    все
    

    начинает работу в состоянии ? : ?(x) =0, ?(y) =2, ?(z) =2, ?(u) = 5, ?(v) =0В каком из следующих состояний ?1 она завершит свою работу?


    Пусть структурированная программа
    P: x:= y+1; z := x+1; x := z+1; y:= y+1; z:= y; z := z +1 ; x := x+1
    начинает работу в состоянии ? : ?(x) =3, ?(y) =5, ?(z) =2В каком из следующих состояний ?1 она завершит свою работу?


    Пусть структурированная программа

    x:= y+1;  v:= u+1;  y := z+1; 
    если  x < v  то
          если  x = y   то
                               y := y+1
                        иначе  y := x 
          конец 
                    иначе  y :=x +1 
    конец
    

    начинает работу в состоянии ? : ?(x) =0, ?(y) =5, ?(z) =5, ?(u) = 6, ?(v) =2В каком из следующих состояний ?1 она завершит свою работу?


    Какие из следующих трех последовательностей операторов являются синтаксически правильными структурированными программами?

  • P1: x := y+1; z:= x + 1; если x +1 < z то y := z иначе y:=x конец
  • P2: x := y+1; z:= x +1; если x = z то y := z иначе y:=x конец
  • P3: x := y+1; u:= z +1; пока u = z +1 делай y := z; u := u+1 все

  • Пусть П+ — это построенная в лекции программа, которая вычисляет функцию Ф+(x,y) = x+y в переменной x, используя одну рабочую переменную zКакие из следующих структурированных программ П1, П2, П3 вычисляют в переменной x квадратный трехчлен p(x)= x2 +2x +2 ?


    Пусть структурированная программа

    P:  
    x:= z +1; y := u+1;  v := y+1;  
    если  x < v  то
          если  x = y   то
                             z := y+1
                        иначе  z := x 
          конец 
                    иначе  z :=x +1 
    конец
    

    начинает работу в состоянии ? : ?(x) =0, ?(y) =3, ?(z) =5, ?(u) = 4, ?(v) =2В каком из следующих состояний ?1 она завершит свою работу?


    Пусть структурированная программа

    P:  
    x:= y+1;  v:= u+1;  
    пока  x < v  делай
      если  y <  x то
                             y := y+1; u := u+1
                      иначе  x := x +1
      конец 
    все
    

    начинает работу в состоянии ? : ?(x) =0, ?(y) =2, ?(u) = 5, ?(v) =0В каком из следующих состояний ?1 она завершит свою работу?


    Пусть структурированная программа

    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 она завершит свою работу?


    Пусть структурированная программа
    P: x:= y+1; z := x+1; y := z+1; y:= y+1; z:= y; z := z +1 ; x := x+1
    начинает работу в состоянии ? : ?(x) = 2, ?(y) =3, ?(z) =2В каком из следующих состояний ?1 она завершит свою работу?


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


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


    Пусть заданы три функции:
    f(x,y,z) = xy +z, g(x,y) = 2x + y, h(x) =2x2
    Какую функцию F(x1,x2) задает выражение
    [f; [h; I21 ] [g; [h; I22 ], I22], I22] ?


    Какое из следующих выражений задает примитивно рекурсивное описание функции f(x) = (x+1)2 ?


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


    Пусть функция F(x) задана примитивной рекурсией
    R(1, h(y,z)), где h(y,z) = [2z/z]Чему равно значение F(5)?


    Пусть c2(x, y) = 2x(2y+1) -1 — это функция нумерации пар, а
    c21(z) и c22(z) — это соответствующие обратные функции такие, что c2(c21(z), c22(z)) = z для всех z. Примитивную рекурсивность этих функций можно использовать для установления рекурсивности функций, значения которых на аргументе (y+1) зависят от их значений в двух предыдущих точках y-1 и y. Рассмотрим функцию F(x), заданную равенствами:
    F(0) = 0, F(1) = 1, F(y+2) = F(y) + F(y+1) +1. Положим G(y) = c2(F(y), F(y+1)). Так как
    F(y) = c21(G(y)), то для доказательства примитивной рекурсивности F достаточно установить примитивную рекурсивность G. Определите, какая из следующих примитивных рекурсий задает G.


    Обозначим через 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) ?


    Пусть функция rm(x, y) = y mod x равна остатку от деления y на x ( rm(0,y)=y )Какое из следующих выражений определяет число dn(x) различных делителей числа x, отличных от 1 и самого x?

    Какое из следующих выражений задает примитивно рекурсивное описание функции f(x) = x2 + x?


    Пусть заданы три функции:
    f(x,y,z) = xy +z, g(x,y) = 2x — y, h(x) =2x2
    Какую функцию F(x1,x2) задает выражение
    [g; [f; I22 , I22 , I21 ], [h;[s1; I22 ]] ?


    Пусть функция rm(x, y) = y mod x равна остатку от деления y на x ( rm(0,y)=y), а функция p(n) принимает значение 1, если число n простое, и равна 0 для составных n (p(0)=p(1)=0, p(2)=p(3)=1, …). Какое из следующих выражений определяет число dp(x) различных простых делителей числа x?


    Пусть c2(x, y) = 2x(2y+1) -1 — это функция нумерации пар, а
    c21(z) и c22(z) — это соответствующие обратные функции такие, что c2(c21(z), c22(z)) = z для всех z. Примитивную рекурсивность этих функций можно использовать для установления рекурсивности функций, значения которых на аргументе (y+1) зависят от их значений в двух предыдущих точках y-1 и yРассмотрим функцию F(x), заданную равенствами:
    F(0) = 1, F(1) = 1, F(y+2) = F(y) + F(y+1) . Положим G(y) = c2(F(y), F(y+1))Так как
    F(y) = c21(G(y)), то для доказательства примитивной рекурсивности F достаточно установить примитивную рекурсивность GОпределите, какая из следующих примитивных рекурсий задает G


    Пусть машина Тьюринга M построена из следующих простых машин Тьюринга:
    Копa –копирует вход после разделительного символа a : w ? w a w;
    Зам(a, b) – заменяет первое слева вхождение символа a на b: w1a w2 ? w1 b w2 ( a ? w1 );
    Сум — складывает два аргумента в унарной системе: |x * |y ? |x+y ;
    Умн — умножает два аргумента в унарной системе: |x * |y ? |xy;
    с помощью операций последовательного и параллельного применения следующим образом:
    M = Коп# ; par#( Коп* , Коп* ); par#( Умн, Сум); Зам(#, *); Сум
    Какую из следующих арифметических функций f(x) (при унарном кодировании аргумента и результата) вычисляет M?


    Приведенные ниже машины Тьюринга Mi (i= 1,2,3,4)

  • M1 = Зам(?, *); Зам(?,|); while Нуль12 do par*( Выч1, Коп#; Зам(#, |); Выч1) enddo; Выб22
  • M2 = Зам(?, *); Зам(?,|); while Нуль12 do par*( Выч1, Коп#; par# (Пуст, Коп#); Зам(#, |); Зам(#, |); Выч1; Выч1) enddo; Выб22
  • M3 =   if  Нуль11 then Пуст 
                else  Коп* Зам(?, *); Зам(?,|); while Нуль13 do par*( Выч1, Коп#, Пуст); 
                par# (Пуст, Умн);  Зам(#, *)) enddo;  Выб33   endif. 
  • M4 =   if  Нуль11 then Пуст 
                else  Коп* Зам(?, *); while Нуль13 do par*( Выч1, Коп#, Пуст); 
                par# (Пуст, Сум);  Зам(#, *)) enddo;  Выб33   endif.
    
  • построены из простых машин Тьюринга Копa , Зам(a, b), Сум, Умн и Пуст, описанных в задаче 4, и машин

  • Выбin – выбирает i-ый аргумент из n аргументов: x1*…*xi*…*xn ? xi ,
  • Нульin — выдает 1, если i-ый аргумент из n аргументов равен ? (нулю) и выдает 0, если этот аргумент не равен 0 (имеет вид |i , i >0),
  • Выч1 – вычитает единицу в унарной системе: |j ? |j-1 (| ? ?, ? ? ?)
  • Какая из этих машин вычисляет функцию f(x) = xx в унарном кодировании, т.е. переводит вход |x в выход |y, где y = xx (пусть f(0)=0) ?

    В конструкции машины Тьюринга со стандартными заключительными конфигурациями нужна служебная машина Тьюринга, назовем ее MOVE, которая сдвигает полученный результат в начальную позицию, отмеченную символом со штрихом. Точнее, MOVE, начав работать в конфигурации вида q a w1 #k#’ (a ??, w1 ??*, k ? 0), должна завершить работу в конфигурации ?kpa’w1 Пусть алфавит ленты MOVE включает символы из ? ? {a’ | a ? ?}? {?, #, #’}, а алфавит состояний Q= {q, p, r} ? {pa | a ? ?}
    Какие из следующих программ выполняют требуемую работу, т.е. могут быть использованы в качестве программы для MOVE ?
    (В текстах программ a и b – это произвольные символы из ?),

    P1: q a >? pa ? П , q a’ >? p a’ Н , pa b >? pb a П, pa b’ >? pb a’ П, pa # >? r a Л, pa #’ >? r a’ Л, pa ? >? r a Л, r a >? r a Л , r a’ >? r a’ Л , r ? >? q ? П.

    P2: q a >? pa ? П , pa b >? pb a П, pa b’ >? pb a’ П, pa # >? r a Л, pa #’ >? r a’ Л, pa ? >? r a Л, r a >? r a Л , r a’ >? r a’ Л , r ? >? q ? П.

    P3: q a >? pa ? П , pa b >? pa b П, pa # >? pa # П, pa #’ >? r a Л, pa b’ >? pa b’ П, pa ? >? r a Л, r a >? r a Л , r a’ >? r a’ Л , r ? >? q ? П, q # >? q ? П , q a’ >? p a’ Н.


    Пусть машина Тьюринга 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 ?


    Приведенные ниже машины Тьюринга Mi (i= 1,2,3,4)

  • M1 = Зам(?, *); Зам(?,|); while Нуль12 do par*( Выч1, Коп#; Зам(#, |); Выч1) enddo; Выб22
  • M2 = Зам(?, *); Зам(?,|); while Нуль12 do par*( Выч1, Коп#; par# (Пуст, Коп#); Зам(#, |); Зам(#, |); Выч1; Выч1) enddo; Выб22
  • M3 =   if  Нуль11 then Пуст 
                else  Коп* Зам(?, *); Зам(?,|); while Нуль13 do par*( Выч1, Коп#, Пуст); 
                par# (Пуст, Умн);  Зам(#, *)) enddo;  Выб33   endif.
  • M4 =   if  Нуль11 then Пуст 
                else  Коп* Зам(?, *); while Нуль13 do par*( Выч1, Коп#, Пуст); 
                par# (Пуст, Сум);  Зам(#, *)) enddo;  Выб33   endif.
  • построены из простых машин Тьюринга Копa , Зам(a, b), Сум, Умн и Пуст, описанных в задаче 4, и машин

  • Выбin – выбирает i-ый аргумент из n аргументов: x1*…*xi*…*xn ? xi ,
  • Нульin — выдает 1, если i-ый аргумент из n аргументов равен ? (нулю) и выдает 0, если этот аргумент не равен 0 (имеет вид |i , i >0),
  • Выч1 – вычитает единицу в унарной системе: |j ? |j-1 (| ? ?)
  • Какая из этих машин вычисляет функцию f(x) = 2x в унарном кодировании, т.е. переводит вход |x в выход |y, где y = 2x?


    Пусть машина Тьюринга 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 1100 ?


    Пусть машина Тьюринга M построена из простых машин Тьюринга Копa , Зам(a, b), Сум, Умн и Пуст, описанных в задаче 4, и машин

  • Выбin – выбирает i-ый аргумент из n аргументов: x1*…*xi*…*xn ? xi ,
  • Большеij — выдает 0, если в аргументе вида |x1 *…*|xi *…*|xj *…*|xn i-ый аргумент xi больше j-ого аргумента xj , иначе выдает 1,
  • с помощью операций последовательного и параллельного применения и конструкции условного оператора следующим образом:

    M =  Коп# ; par#( par* (Коп*, Пуст ); Зам(*, |), Пуст );
    if  Больше21  then par#(  Пуст, Умн ) else  par#(  Пуст, Сум ) endif;
    Зам(#, *); Выб33.

    Какие результаты она получит на входных данных вида |x1 * |x2
    при x1 = 4, x2 = 8
    и при x1 = 1, x2 = 5, соответственно?


    В доказательстве теоремы 20.1 для построения м.Т., реализующей оператор примитивной рекурсии F(x,y) = R( g1, f3), требовалась м.Т. M2, которая переводит конфигурацию вида |y *|x* |u* |z в конфигурацию |y *|x* |u+1* |f(x,u,z) , используя м.Т. Mf, вычисляющую функцию f(x,u,z).
    Какие из следующих программ м.Т. выполняют требуемую работу, т.е. могут быть использованы в качестве программы для M2 ?

  • P1 = Зам(*,# ); par# ( Пуст, Коп#); par# (Пуст, Пуст, Mf ); Зам( #,* ); Зам( #,* )
  • P2 = Зам(*,# ); par# ( Пуст, Коп#); par# (Пуст, Пуст, Mf ); par# (Пуст, par* (Пуст, +1, Чист), Пуст); Зам( #,* ); Зам(?, |); Зам( #,| ); par* (Пуст, Пуст, Пуст, Выч1; Выч1)
  • P3 = Зам(*,# ); par# ( Пуст, Коп#); par# (Пуст, par* (Пуст, +1, Чист), Mf ); par* (Зам( #,* ), Пуст, Зам(?, |); Зам( #,| ); Выч1; Выч1)
  • В этих определениях участвуют следующие простые машины Тьюринга:

  • Копa –копирует вход после разделительного символа a : w ? w a w;
  • Зам(a, b) – заменяет первое слева вхождение символа a на b: w1a w2 ? w1 b w2 ( a ? w1 );
  • Пуст — не изменяет аргумент: w ? w ;
  • Чист – стирает аргумент: w ? ? ;
  • Выч1 – вычитает единицу в унарной системе: |j ? |j-1 (| ? ?, ? ? ?);
  • +1 — прибавляет 1 к аргументу: |x? |x+1

  • В доказательстве теоремы 20.2 для построения м.Т MП, моделирующей работу структурированной программы П с переменными x1, … , xm, используются м.Т. Mij (1 ? i, j ? m), которые реализуют присваивание xi := xj, т.е. переписывают содержимое j-го этажа ленты на i-ый. Пусть m=4, i=2, j=4.
    Пусть ? = { < a1, a2, a3, a4> | ai ? {?, |}, i=1,2,3,4 } – алфавит ленты, а Q={ q, s, p },– множество состояний M24, в котором q — начальное, а p – заключительное состояние.
    Какие из следующих программ могут быть использованы в качестве программы для M24 ?
    (В текстах программ 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, ?> П.

  • Согласно тезису Тьюринга-Черча язык структурированных программ является универсальным – для любой вычислимой функции в нем имеется вычисляющая ее программа. Всякий язык программирования, в котором выразимы все операторы языка структурированных программ, также является универсальным. Некоторые из операторов языка структурированных программ оказываются «лишними» — они выразимы через остальные, т.е. язык сохраняет универсальность и при их удалении.
    Определите, какие из следующих видов операторов (по отдельности) можно выразить через остальные операторы языка.

  • (a) если x < y то P1 иначе P2 конец,
  • (b) если x = y то P1 иначе P2 конец.,
  • (c) x := 0.

  • В доказательстве теоремы 10.1 для построения м.Т., реализующей оператор примитивной рекурсии F(x,y) = R( g1, f3), требовалась м.Т. M1, которая переводит конфигурацию вида |x* |y в конфигурацию |y * |x* ? *|g(x) , используя м.Т. Mg,
    вычисляющую функцию g(x).
    Какие из следующих программ м.Т. выполняют требуемую работу, т.е. могут быть использованы в качестве программы для M1 ?

  • P1 = Коп# ; par# (par* (Чист, Пуст); Зам(*,? ) , par* (Пуст ,Чист); Зам(*,? ) ); par# (Пуст, Коп* ); par* (Пуст, +1; +1; Зам(|,? ); Зам(|,* )); par* (Пуст, Пуст, Mg); Зам( #,* )
  • P2 = Коп# ; par# (par* (Чист, Пуст); Зам(*,? ) , par* (Пуст ,Чист); Зам(*,? ) ); par# (Пуст, Коп# ); par# (Пуст, Пуст, Mg ; +1; +1; Зам(|,? ); Зам(|,* )); Зам( #,* ); Зам( #,* )
  • P3 = Коп* ; par* (Чист, Пуст, Пуст ,Чист); Зам(*,? ); Зам(*,# ); Зам(*,? ); par# (Пуст, Mg ; +1; +1; Зам(|,? ); Зам(|,* )); Зам( #,* )
  • В этих определениях участвуют следующие простые машины Тьюринга:

  • Копa – копирует вход после разделительного символа a : w ? w a w;
  • Зам(a, b) – заменяет первое слева вхождение символа a на b: w1a w2 ? w1 b w2 ( a ? w1 );
  • Пуст – не изменяет аргумент: w ? w ;
  • Чист – стирает аргумент: w ? ? ;
  • +1 – прибавляет 1 к аргументу: |x ? |x+1

  • Согласно тезису Тьюринга-Черча язык структурированных программ является универсальным – для любой вычислимой функции в нем имеется вычисляющая ее программа. Всякий язык программирования, в котором выразимы все операторы языка структурированных программ, также является универсальным. Некоторые из операторов языка структурированных программ оказываются «лишними» — они выразимы через остальные, т.е. язык сохраняет универсальность и при их удалении.
    Определите, какие из следующих видов операторов (по отдельности) можно выразить через остальные операторы языка.

  • (a) x := x +1,
  • (b) пока x < y делай P все,
  • (c) пока x = y делай P все.
  • .


    В доказательстве теоремы 20.2 для построения м.Т MП, моделирующей работу структурированной программы П с переменными x1, … , xm, используются м.Т. Mij (1 ? i, j ? m), которые реализуют присваивание xi := xj, т.е. переписывают содержимое j-го этажа ленты на i-ый. Пусть m=4, i=3, j=1.
    Пусть ? = { < a1, a2, a3, a4> | ai ? {?, |}, i=1,2,3,4 } – алфавит ленты, а Q={ q, s, p },– множество состояний M31, в котором q — начальное, а p – заключительное состояние.
    Какие из следующих программ могут быть использованы в качестве программы для M31 ?
    (В текстах программ 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 > Л ,
  • P2: : q <|, b, c, d > >? q < |, b , c, d > П , s < ? , b, |, d > >? s < | , b, ?, d > Л , q <a, b, |, d > >? q < a, b, |, d > П , s < ?, ?, ?, ?> >? p < ?, ?, ?, ?> П. q < ?, b, ?, d> >? s < ? , b, ?, d > Л , s < | , b, c, 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 < ?, ?, ?, ?> П.

  • Какими из следующих свойств обладает отношение алгоритмической сводимости A ?m B ?

  • (a) является отношением эквивалентности,
  • (b) рефлексивно и транзитивно,
  • (c) сохраняет свойство разрешимости: если A ? m B и B — разрешимо, то и A разрешимо.

  • В теореме 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′.

  • В доказательстве теоремы 20.1 для построения м.Т., реализующей оператор примитивной рекурсии F(x1,x2, y) = R( g2, f4), требовалась м.Т. M1, которая переводит конфигурацию вида |x1*|x2* |y в конфигурацию |y * |x1*|x2* ? *|g(x) , используя м.Т. Mg, вычисляющую функцию g(x1,x2).
    Какие из следующих программ м.Т. выполняют требуемую работу, т.е. могут быть использованы в качестве программы для M1 ?

  • P1 = Коп# ; par# (par* (Чист, Чист,Пуст); Зам(*,? ) , par* (Пуст , Пуст ,Чист); Зам(*,# ) ; Зам(*,? ) ; Зам( #,* )); par# (Пуст, Коп* ); par* (Пуст, Mg ; +1; +1; Зам(|,? ); Зам(|,* ))
  • P2 = Коп# ; par# (par* (Чист, Чист , Пуст); Зам(*,? ) ; Зам(*,? ), par* (Пуст , Пуст ,Чист); Зам(*,# ) ; Зам(*,? ) ; Зам( #,* )); par# (Пуст, Коп# ); par# (Пуст, Пуст, Mg ; +1; +1; Зам(|,? ); Зам(|,* )); Зам( #,* ); Зам( #,* )
  • P3 = Коп* ; par* (Чист, Чист, Пуст, Пуст, Пуст ,Чист); Зам(*,? ); Зам(*,# ); Зам(*,? ); par# (Пуст, Mg ; +1; +1; Зам(|,? ); Зам(|,* )); Зам( #,* )
  • В этих определениях участвуют следующие простые машины Тьюринга:

  • Копa –копирует вход после разделительного символа a : w ? w a w;
  • Зам(a, b) – заменяет первое слева вхождение символа a на b: w1a w2 ? w1 b w2 ( a ? w1 );
  • Пуст — не изменяет аргумент: w ? w ;
  • Чист – стирает аргумент: w ? ? ;
  • +1 — прибавляет 1 к аргументу: |x? |x+1


  • Какую булеву функцию реализует эта логическая схема в вершине a?


    Пусть задана логическая схема S=(V, E) :
    V= {a (X), b(Y), c(Z), d(V), e(¬), f(?),g(?),h(¬), i(¬), k(?), m(?) } (после имени вершины в скобках указана ее метка — переменная или булева функция),
    E= { (a, i), (b, f), (b, k), (c, g), (d, e), (e, g), (f, h), (g, k), (h, m), (i, f), (k, m) }.
    Какие из следующих линейных программ вычисляют в переменной Z ту же функцию F(X,Y,Z,V), что и схема S в вершине m?

    P1:                       P2:                        P3:
    X = ¬X;                   i = ¬X;                    X = ¬X;
    V = ¬V;                   e = ¬V;                    X = X ? Y;
    X = X ? Y;                f = i ? Y;                 X = ¬X;  
    Z = Z ? V;                h = ¬i;                    V = ¬V;
    X = ¬X;                   g = Z ? e;                 V = Z ? V;
    Y = Y ? Z;                k = Y ? g;                 V = Y ? V;
    Z = X ? Y.                Z = h ? k.                 Z = X ? V.
    


    Какая из следующих формул задает булеву функцию, которую реализует эта диаграмма?


    На следующем рисунке представлены диаграммы двух конечных автоматов 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,1), (p,2)}, ?D >,


    Пусть язык L в алфавите {a, b}, состоит из всех слов, которые заканчиваются на abb и содержат число символов b кратное 3, и пусть гоморфизм
    h: {0, 1,2}* >? {a, b}* задан равенствами: h(0) = bab, h(1) = b, h(2) = ? Какие из следующих трех слов принадлежат прообразу h-1(L) языка L при гомоморфизме h?
    W1 = 210102012, W2 = 201000201021, W3 = 021010212

    Используя теорему о разрастании, установите, какие из следующих трех языков в алфавите {a, b} не являются автоматными.

    L1 = { wbw | w = an , n > 0 },

    L2 = { bwwb | w = an , n > 0 },

    L3 = { (ab)nam | n, m > 0 }.


    Пусть язык L в алфавите {a, b}, состоит из всех слов, которые начинаются на aa и содержат число символов a кратное 3, и пусть гоморфизм h: {0, 1,2}* >? {a, b}* задан равенствами: h(0) = aaa, h(1) = ba, h(2) = ? Какие из следующих трех слов принадлежат прообразу h-1(L) языка L при гомоморфизме h?

    W1 = 21112, W2 = 20101012, W3 = 00211011


    Используя теорему о разрастании, установите, какие из следующих трех языков в алфавите {a, b} не являются автоматными.

    L1 = { ww | w = b2anb , n > 0 },

    L2 = { b2anb | n > 0 },

    L3 = { (ab)nanb | n > 0 }.


    Пусть структурированная программа

    P:  
    x:= y+1;  v:= u+1;  
    пока  x < v  делай
       если  y <  x то
                           y := y+1
                    иначе  x := x +1; u := u+1
       конец 
    все
    

    начинает работу в состоянии ? : ?(x) = 2, ?(y) =3, ?(u) = 5, ?(v) =0В каком из следующих состояний ?1она завершит свою работу?


    Какие из следующих трех последовательностей операторов являются синтаксически правильными структурированными программами?

  • P1: x := y+1; z:= 1; если x < z то y := z иначе y:=x конец
  • P2: x := y+1; z:= x +1; если x < z то y := z иначе y:=x конец
  • P3: x := y+1; z:= x +1; пока u < z делай y := z; u := u+1 все

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


    Предположим, что в некоторой конфигурации машины Тьюринга M на ленте записано слово w в алфавите ?, не содержащем символов ? и *, но головка «заблудилась» – она наблюдает символ ? и не знает левее или правее слова w находится.
    Какие из следующих программ помогут найти начало слова w, т.е. любую конфигурацию вида q ?k w или w?k q ? (k > 0) переведут в конфигурацию q’w ?
    (В текстах программ a – это произвольный символ из ?, используемые состояния: q, q’, l, r, l1, r1 , l2 , r2, l3, r3, l4)

    P1: q ? >? l1 * Л, l1?>? r * П, l1a>? l2a П, l2 a>? l2 a Л, l2 ?>? q’? П, r? >? r ? П, r *>? r1 ? П, r1 ?>? l * Л, l ?>? l ? Л, l *>? l1 ? Л, r1 a>? r2a Л, r2 ?>? r2? Л, r2 *>? r3? П, r3?>? r3? П, r3 a>? q’a Н.

    P2: q ? >? l1 * Л, l1?>? r * П, l1a>? l2a П, l2 ?>? l2? П, l2 *>? l3? Л, l3 ?>? l3? Л, l3 a>? q’a Н,
    r? >? r ? П, r *>? r1 ? П, r1 ?>? l * Л, l ?>? l ? Л, l *>? l1 ? Л,
    r1 a>? r2a Л, r2 ?>? r2? Л, r2 *>? r3? П, r3?>? r3? П, r3 a>? q’a Н.

    P3: q ? >? l1 * Л, l1?>? r * П, l1a>? l2a П, l2 ?>? l2? П, l2 *>? l3? Л, l3 ?>? l3? Л, l3 a>? l4 a Л,
    l4 a>? l4 a Л, l4 ?>? q’? П, r? >? r ? П, r *>? r1 ? П, r1 ?>? l * Л, l ?>? l ? Л, l *>? l1 ? Л,
    r1 a>? r2a Л, r2 ?>? r2? Л, r2 *>? r3? П, r3?>? r3? П, r3 a>? q’a Н.


    Пусть машина Тьюринга 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 ?


    Три машины Тьюринга Mi = < ?, Q !, Pi, q, !> (i = 1,2, 3), имеют общий алфавит ленты ?={ ?, a, b}, алфавит состояний Q = { q, p, r, s, !}, начальное состояние q, заключительное состояние ! и следующие программы:

    Какие из этих машин переводят любую начальную конфигурацию вида q a2n b в заключительную конфигурацию ! b an (n ? 0 )?


    Три машины Тьюринга Mi = < ?, Q !, Pi, q, !> (i = 1,2, 3), имеют общий алфавит ленты ?={ ?, a, b}, алфавит состояний Q = { q, p, r, s, !}, начальное состояние q, заключительное состояние ! и следующие программы:

    Какие из этих машин переводят любую начальную конфигурацию вида q an b в заключительную конфигурацию ! b a2n (n ? 0 )?


    В конструкции для параллельной композиции машин Тьюринга на этапах 3 и 5 участвует служебная машина, назовем ее CHANGE, меняющая местами аргументы, точнее переводящая любую конфигурацию вида x * q y (x и y – слова в алфавите ?, не содержащем символов ?, * и # , q – начальное состояние) в конфигурацию
    y* q’ x (q’ – заключительное состояние). Пусть Q={ q, s, p, r, q’}? {pa | a ? ?} – множество состояний CHANGE. Какие из следующих программ выполняют требуемую работу, т.е. могут быть использованы в качестве программы для CHANGE ?
    (В текстах программ a – это произвольный символ из ?, а b — это произвольный символ из ? ? {*, #} ).

    P1: q b >? q b П , q ? >? s # Л, s b >? s b Л, s ? >? p ? П, p a >? pa ?П, p * >? r ?П, pa b >? pa b П, pa ? >? s a Л, r a >? r a П , r # >? q’ * П.

    P2: q a >? q a П , q ? >? s * Л, s b >? s b Л, s ? >? p ? П, p a >? pa ?П, p * >? r ?П, pa b >? pa b П, pa ? >? s a Л, r a >? r a П , r*>? q’ * П.

    P3: q a >? q a П , q ? >? s * Л, s b >? s b Л, s ? >? p ? П, p a >? pa ?П, p * >? q’ * П, pa b >? pa b П, pa ? >? s a Л.


    Пусть машина Тьюринга M построена из следующих простых машин Тьюринга:

  • Копa –копирует вход после разделительного символа a : w ? w a w;
  • Зам(a, b) – заменяет первое слева вхождение символа a на b: w1a w2 ? w1 b w2 ( a ? w1 );
  • Сум — складывает два аргумента в унарной системе: |x * |y ? |x+y ;
  • Умн — умножает два аргумента в унарной системе: |x * |y ? |xy ;
  • Пуст — не изменяет аргумент: w ? w
  • с помощью операций последовательного и параллельного применения следующим образом:

    M = Коп# ; par#( Коп* , Коп* ); par#( Умн, Сум); par#( Коп* ; Сум , Пуст ); Зам(#,?); Сум

    Какую из следующих арифметических функций f(x) (при унарном кодировании аргумента и результата) вычисляет M?


    Пусть машина Тьюринга M построена из простых машин Тьюринга Копa , Зам(a, b), Сум, Умн и Пуст, описанных в задаче 4, и машин

  • Выбin – выбирает i-ый аргумент из n аргументов: x1*…*xi*…*xn ? xi ,
  • Большеij — выдает 0, если в аргументе вида |x1 *…*|xi *…*|xj *…*|xn i-ый аргумент xi больше j-ого аргумента xj , иначе выдает 1,
  • с помощью операций последовательного и параллельного применения и конструкции условного оператора следующим образом:

    M =  Коп# ; par#( par* (Коп*, Пуст ); Зам(*, |), Пуст );
    if  Больше21  then par#(  Пуст, Сум  ) else  par#(  Пуст, Умн ) endif;
    Зам(#, *); Выб33.

    Какие результаты она получит на входных данных вида |x1 * |x2
    при x1 = 2, x2 = 7
    и при x1 = 3, x2 = 5, соответственно?


    В доказательстве теоремы 20.2 для построения м.Т MП, моделирующей работу структурированной программы П с переменными x1, … , xm, используются м.Т. Mij (1 ? i, j ? m), которые реализуют присваивание xi := xj, т.е. переписывают содержимое j-го этажа ленты на i-ый. Пусть m=4, i=3, j=1.
    Пусть ? = { < a1, a2, a3, a4> | ai ? {?, |}, i=1,2,3,4 } – алфавит ленты, а Q={ q, s, p },– множество состояний M43, в котором q — начальное, а p – заключительное состояние.
    Какие из следующих программ могут быть использованы в качестве программы для M43 ?
    (В текстах программ 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 < ?, ?, ?, ?> П ,
  • P2: : q <a, b, c, | > >? q < a, b , c, | > П , s < a , b, |, d > >? s < a , b, |, | > Л , q <a, b, |, d > >? q < a, b, |, d > П , s < ?, ?, ?, ?> >? p < ?, ?, ?, ?> П. q <a, b, ?, ?> >? s < a , b, ?, ? > Л , s < a , b, ?, | > >? s < a , b, ?, ? > Л,
  • 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 > Л ,

  • Какими из следующих свойств обладает отношение алгоритмической сводимости A ?m B ?

  • (a) если A ?m B, то (N \A) ?m (N \B) ,
  • (b) A ?m C и B ?m C для C= {2x | x ? A} ? {2x+1 | x ? B},
  • (c) сохраняет свойство неразрешимости: если A ?m B и A — неразрешимо, то и B неразрешимо .

  • В теореме 20.5 была доказана неразрешимость проблемы останова:
    по произвольной структурированной программе П определить завершится ли вычисление П на входе 0. Пусть Mh0= {n | ФПn,y (0) < ?} – это (неразрешимое) множество номеров программ, которые останавливаются на входе =0. Рассмотрим проблему определения по структурированной программе бесконечности множества ее результатов:
    Minf = {n | множество значений ФПn,y (x) бесконечно}.
    Какие из следующих функций сводят Mh0 к Minf ?

  • f1(n) = номер программы: ‘ x:= 0; Пn ; y:= x ‘.
  • f2(n) = номер программы: ‘xn:=x; x:= 0; Пn ; y:= xn . (здесь переменная xn не входит в Пn )
  • f3(n) = номер программы: ‘y:= x; x:= 0; Пn ; y:= y+1′.

  • Пусть задана линейная программа 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.
  • Постройте логическую схему SP со входами X1, X2, X3 и функциональными вершинами, соответствующими командам P, вычисляющую ту же функцию, что и P в выходной переменной Z. Чему равна ее глубина?



    Какую булеву функцию реализует эта диаграмма?
    (В ответах функции заданы последовательностями 8 нулей и единиц — их значениями на лексикографически упорядоченных наборах значений аргументов x1, x2 и x3)


    На следующем рисунке представлены диаграммы двух конечных автоматов 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,1), (p,2)}, ?D >,


    Заданы два НКА:

    A =< {a, b}, {0, 1, 2, 3}, 0, {2}, ?A > с программой
    ?A: 0 a >? 1, 0 a >? 2, 0 b >? 0, 1 a >? 2, 1 b >? 1, 2 a >? 3, 2 b >? 2, 3 a >? 3, 3b >? 3 и

    B =< {a, b}, {q0, q1, q2}, q0, {q2}, ?B > с программой ?B: q0 a >? q1, q1 b >? q0,
    q1 a >? q2, q2 b >? q1

    Какие из следующих трех НКА С1 , С2 , С3 распознают конкатенацию LA? LB языков, распознаваемых автоматами A и B?
    С1 = < {a,b}, {0, 1, 2, 3, q0, q1, q2}, 0, F1={ q2}, ?1>, С2 = < {a,b}, {0, 1, 2, 3, q0, q1, q2}, 0,
    F2={ q2}, ?2>, С3 = < {a,b}, {0, 1, 2, 3, q0, q1, q2}, 0, F3={ q2}, ?3>, где программы заданы в следующих таблицах (? означает отсутствие соответствующего перехода).


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

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

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

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

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



    Какой язык L является конкатенацией двух языков:
    L1= {a, ab, abba} и L2= { ?, a, b, ba}?


    Пусть S={aaa, aab, aba, abb, baa, bab, bba, bbb} Какая из следующих фраз описывает итерацию S* этого языка?


    Какое из следующих регулярных выражений задает все слова из 0-ей и 1-иц, в которых есть по крайней мере два подряд идущих 0 ?


    Пусть язык L в алфавите {a, b}, состоит из всех слов, которые заканчиваются на aa и содержат число символов b кратное 4, и пусть гоморфизм
    h: {0, 1,2}* >? {a, b}* задан равенствами: h(0) = bab, h(1) = a, h(2) = ? Какие из следующих трех слов принадлежат прообразу h-1(L) языка L при гомоморфизме h?
    W1 = 211100112, W2 = 201010121, W3 = 0021010211

    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>,

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



    Пусть функция F(x) задана примитивной рекурсией
    R(1, h(y,z)), где h(y,z) = [2z+1/z]Чему равно значение F(3)?


    Comments are closed.

    Яндекс.Метрика