71. Задание
В ассоциативном исчислении два слова называются смежными:
1. Если одно из них может быть преобразовано в другое применением подстановок
2. Когда существует цепочка от одного слова к другому и обратно
3. Когда они дедуктивны
4. Если одно из них может быть преобразовано в другое однократным применением допустимой подстановки
72. Задание
В алгоритме Маркова дана цепочка Р Р1, Р2,..., Рn. Если слова Р1, Р2,..., Рn смежные, то цепочка называется:
1. Ассоциативной
2. Эквивалентной
3. Индуктивной
4. Дедуктивной
73. Задание
В алгоритме Меркова дана цепочка Р Р1, Р2,...Рк. Если слова Р1, Р2,...,Рк смежные и цепочка существует и в обратную сторону, то слова Р1 и Рк называют:
1. Ассоциативными
2. Эквивалентными
3. Индуктивными
4. Дедуктивными
74. Задание
В алгоритмах Маркова дана система подстановок в алфавите Л={a,b,c}: abc - c; ba - cb; ca - ab. Преобразуйте с помощью этой системы слово bacaabc
1. cbc
2. ccbcbbc
3. cbacba
4. cbabc
75. Задание
В алгоритмах Маркова дана система подстановок в алфавите A={a, b, c}: cb - abc; bac - ac; cab - b. Преобразуйте с помощью этой системы слово bcabacab:
1. ccb
2. cab
3. cbc
4. bcaab
76. Задание
Вобери правильный ответ
Способ композиции нормальных алгоритмов будет суперпозицией, если:
1. Существует алгоритм С, преобразующий любое слово р, содержащееся в пересечении областей определения алгоритмов А и В
2. Выходное слово первого алгоритма является входным для второго
3. Алгоритм D будет суперпозицией трех алгоритмов ABC, причем область определения D является пересечением областей определения алгоритмов A B и C, а для любого слова р из этого пересечения D(p)= A(p), C(p)=e, D(p)=B(p), если C(p)=е, где е - пустая строка
4. Существует алгоритм С, являющийся суперпозицией алгоритмов А и Д такой, что для любого входного слова р С(р) получается в результате последовательного многократного применения алгоритма А до тех пор, пока не получится слово, преобразуемое алгоритмом В
77. Задание
Способ композиции нормальных алгоритмов будет объединением, если:
1. Входное слово первого алгоритма является входным для второго
2. Существует алгоритм С, преобразующий любое слово р, содержащееся в пересечении областей определения алгоритмов А и В
3. Алгоритм В будет суперпозицией трех алгоритмов АВС, причем область определения D является пересечением областей определения алгоритмов А В и С, а для любого слова р из этого пересечения D(р)=А(р), C(p)=e, D(p)=B(p), если С(р)=е, где е - пустая строка
4. Существует алгоритм С, являющийся суперпозицией алгоритмов А и Д такой, что для любого входного слова р С(р) получается в результате последовательного многократного применения алгоритма А до тех пор, пока не получится слово, преобразуемое алгоритмом В
78. Задание
Способ композиции нормальных алгоритмов будет разветвлением, если:
1. Выходное слово первого алгоритма является входным для второго
2. Существует алгоритм С, преобразующий любое слово р, содержащееся в пересечении областей определения алгоритмов А и В
3. Алгоритм Д будет суперпозицией трех алгоритмов АВС, причем область определения Д является пересечением областей определения алгоритмов А В и С, а для любого слова р из этого пересечения Д(р)=А(р), если С(р)=е, Д(р)=В(р), если С(р)=е, где е - пустая строка
4. Существует алгоритм С, являющийся суперпозицией алгоритмов А и В, такой, что для любого входного слова р С(р) получается в результате последовательного многократного применения алгоритма А до тех пор, пока не получится слово, преобразуемое алгоритмом В
79. Задание
Способ композиции нормальных алгоритмов будет итерацией, если:
1. Выходное слово первого алгоритма является входным для второго
2. Существует алгоритм С, преобразующий любое слово р, содержащееся в пересечении областей определения алгоритмов А и В
3. Алгоритм Д будет суперпозицией трех алгоритмов АВС, причем область определения Д является пересечением областей определения алгоритмов А В С, а для любого слова р из этого пересечения Д(р)=А(р), если С(р)=е, Д(р)=В(р), если С(р)=е, где е - пустая строка
4. Существует алгоритм С, являющийся суперпозицией алгоритмов А и В, такой, что для любого входного слова р С(р) получается в результате последовательного многократного применения алгоритма А до тех пор, пока не получится слово, преобразуемое алгоритмом В