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



Авторы специализируются на тестах по любым дисциплинам! Средний балл по тестам 4,6.
 
Любые вопросы по дистанционному обучению. Тесты, письменные работы, сессия под ключ.
 
Известный интернет сайт, помощь по любым учебным вопросам - от теста до дипломной работы. Личный менеджер.
 
Крупная биржа студенческих работ. Закажи напрямую у преподавателя. Низкие цены, стена заказов.
 
Биржа студенческих работ. Потребуется самостоятельная выгрузка работ.
 

Пусть задана логическая схема 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.

  • только P3
  • (Правильный ответ) только P2 и P3
  • только P2
  • только P1
  • только P1 и P3
  • только P1 и P2
  • P1, P2 и P3

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

  • (Правильный ответ) 11
  • 17
  • 12
  • 15
  • 14

Пусть задана логическая схема 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)

  • (00011101)
  • (Правильный ответ) (01011101)
  • (01010101)
  • (01110101)
  • (01011001)

Пусть задана линейная программа 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. Чему равна ее глубина?

  • (Правильный ответ) 4
  • 6
  • 5
  • 2
  • 3

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

  • только S2
  • только S1
  • только S3
  • ни одна
  • S2 и S3
  • (Правильный ответ) S1 и S3
  • S1 и S2

Пусть задана линейная программа 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. Чему равна ее глубина?

  • 5
  • (Правильный ответ) 3
  • 4
  • 2
  • 6

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

  • ни одна
  • S1 и S2
  • S1 и S3
  • только S2
  • только S1
  • (Правильный ответ) только S3
  • S2 и S3


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

  • (X1 ? X3) ? (X2 ?¬X3)
  • (X1 ? X3) ? (X2? X3)
  • (X1 ? ¬X2 ? X3) ? (X2 ? X3))
  • (X1 ? X2) ?(X2 ?X3)
  • X2 ? ¬X3
  • (Правильный ответ) (X2 ? ¬X3) ? (X1 ?¬X2 ? X3)

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

  • только D1
  • только D2
  • D1 и D2
  • (Правильный ответ) D2 и D3
  • D1 и D3
  • только D3
  • все

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

  • 10
  • 8
  • 11
  • (Правильный ответ) 9
  • 7


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

  • (Правильный ответ) (01010111)
  • (01011011)
  • (01011101)
  • (01011101)
  • (01000111)

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

  • 10
  • 7
  • (Правильный ответ) 6
  • 8
  • 9


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

  • (01011101)
  • (00011101)
  • (Правильный ответ) (01010001)
  • (01011001)
  • (01010101)

Пусть задана УБДР 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 эквивалентную ей сокращенную УБДР и укажите ее сложность.

  • (Правильный ответ) 3
  • 1
  • 4
  • 5
  • 6

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

  • A2 и A3
  • только A2
  • A1 и A2
  • только A1
  • (Правильный ответ) только A3
  • A1 и A3

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

  • только A3
  • (Правильный ответ) только A1
  • только A2
  • A2 и A3
  • A1 и A2
  • A1 и A3

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

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

  • W и V
  • только U
  • V и U
  • только W
  • только V
  • (Правильный ответ) все
  • W и U

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

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

  • все слова вида (aba)na при n= 1, 2, 3, …
  • все слова вида (ab)na при n=0, 1, 2, 3, …
  • (Правильный ответ) все слова вида (ab)naa при n=0, 1, 2, 3, …
  • все слова, начинающиеся на a и заканчивающиеся на a
  • все слова, начинающиеся на ab и заканчивающиеся на 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 >,

  • C, LC = LA ? LB
  • D, LD = LA ? LB
  • D, LD = LA ? LB
  • C, LC = LA \ LB
  • (Правильный ответ) D, LD = LA \ LB
  • C, LC = LB \ LA

Пусть задан недетерминированный конечный автомат
(без пустых переходов)
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 >? ?

  • M1 и M3
  • только M2
  • M2 и M3
  • только M3
  • ни один
  • (Правильный ответ) M1 и M2
  • только M1

Пусть задан недетерминированный конечный автомат
(без пустых переходов)
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 >??

  • M1 и M2
  • только M1
  • ни один
  • (Правильный ответ) M1 и M3
  • только M2
  • M2 и M3
  • только M3

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

  • C, LC = LA \ LB
  • D, LD = LA \ LB
  • D, LD = LA ? LB
  • (Правильный ответ) D, LD = LA ? LB
  • C, LC = LB \ LA
  • C, LC = LA ? LB

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

  • D, LD = LA ? LB
  • (Правильный ответ) D, LD = LA ? LB
  • D, LD = LA \ LB
  • C, LC = LA ? LB
  • C, LC = LB \ LA
  • C, LC = LA \ LB

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

  • D, LD = LA ? LB
  • D, LD = LA \ LB
  • C, LC = LA ? LB
  • D, LD = LA ? LB
  • (Правильный ответ) C, LC = LB \ LA
  • C, LC = LA \ LB

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

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>, где программы заданы в следующих таблицах (? означает отсутствие соответствующего перехода).

  • C2 и C3
  • только C2
  • только C1
  • все
  • C1 и C3
  • (Правильный ответ) C1 и C2
  • только C3

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

  • L = {?, a, b, ba, bb, ab, bab, aba, abba, abb, abba, abbb}
  • L = {?, a, b, ba, bb, bba, aba, abbaa, ab, abb, abbab, abbaba}
  • L = {a, b, ba, bb, bba, aba, abb, abba, abba, abab}
  • (Правильный ответ) L = {?, a, b, ba, bb, bba, ab, aba, abba , baa, bab, baba}
  • L = {a, ab, abba, aa, aba, abbaa, abb, abbab, abbaba}

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

  • cbn+2
  • banbn+4aaa
  • (Правильный ответ) bn+2canc
  • bncanbbb
  • cnbbbaaabb

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

  • canbn+3c
  • bbbcnaabb
  • bcbn+4anaca
  • bn+2canc
  • (Правильный ответ) ancbn+3c

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

  • все слова четной длины в алфавите {0, 1}, содержащие подслово 0000
  • все слова четной длины в алфавите {0, 1}, заканчивающиеся на 10, в которых на четных местах стоят нули
  • все слова в алфавите {0, 1}, заканчивающиеся на 10, в которых на нечетных местах стоят нули и которые содержат подслово 0000
  • все слова в алфавите {0, 1}, заканчивающиеся на 10, с длиной > 5
  • (Правильный ответ) все слова в алфавите {0, 1}, заканчивающиеся на 10, в которых на четных местах стоят нули и которые содержат подслово 0000

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

  • 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 все

 

  • (Правильный ответ) только P2
  • только P3
  • P2 и P3
  • P1 и P3
  • все
  • P1 и P2
  • только P1

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

  • П1 и П3
  • только П1
  • только П2
  • (Правильный ответ) все
  • П1 и П2
  • П2 и П3
  • только П3

Пусть структурированная программа
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 она завершит свою работу?

  • ?1(x) = 6, ?1(y) = 7, ?1(z) = 8
  • ?1(x) = 5, ?1(y) = 6, ?1(z) = 7
  • ?1(x) = 5, ?1(y) = 7, ?1(z) = 7
  • ни в одном из вышеуказанных
  • (Правильный ответ) ?1(x) = 5, ?1(y) = 7, ?1(z) = 8

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

  • ни одно из выше перечисленных
  • (Правильный ответ) R( 1, [+; [s1 ;[ s1 ;[ s1 ;[+; I21, I21]]]], I22 ])
  • <s