Font size
WorksheetsАлгорифмы Маркова
Total questions: 15
Worksheet time: 36mins
Определите результат действия на слово P = 1099 нормального
алгорифма, заданного в алфавите
A={0,1,2,3,4,5,6,7,8,9}
с
использованием дополнительных символов a и b, со схемой
Z =| 0b →. 1 | 1b →. 2 |
| 2b →. 3 | 3b →. 4 |
| 4b →. 5 | 5b →. 6 |
| 6b →. 7 | 7b →. 8 |
| 8b →. 9| 9b → b0 |
| b →. 1 | a0 → 0a |
| a1 → 1a | a2 → 2a |
| a3 → 3a | a4 → 4a |
| a5 → 5a | a6 → 6a |
| a7 → 7a | a8 → 8a |
| a9 → 9a | 0a → 0b |
| 1a → 1b | 2a → 2b |
| 3a → 3b | 4a → 4b |
| 5a → 5b | 6a → 6b |
| 7a → 7b | 8a → 8b |
| 9a → 9b | Λ → a |
1100
1001
1010
1008
Определите результат действия на слово P = abbaa нормального алгорифма, заданного в алфавите
A={a,b}
с использованием дополнительного символа *, со схемой
Z=| *a → aa* | *b → bb* |
| a* →. Λ | b* →. Λ |
| * →. Λ | Λ → * |
aabbbbaaa
aabbbbaaaa
abbaa
aaabbbbbbaaaa
Определите результат действия на слово P = abbbbaa нормального алгорифма, заданного в алфавите A={a,b} с использованием дополнительного символа *, со схемой
Z = |*aa → *a | *ab → *a |
| *ba → *b | *bb → *b |
| * →. Λ | Λ → * |
a
b
*
Λ
Нормальный алгорифм со схемой
Z = | b → a | aaa → a |
| aa →. aa | Λ → Λ |
задан в алфавите
A = {a,b}.
Определить, для каких слов алгорифм завершится за конечное число шагов
Λ
bababaab
aaabbbaaabbba
baabaababa
bbbaaabbaa
Нормальный алгорифм со схемой
Z = | aaaaaa → Λ | aaa → aaa |
| aa →. aa | Λ → Λ |
задан в алфавите
A = {a}.
Определить наименьшую длину слова, к которому применим алгоритм, если длина слова не может быть меньше 40
44
42
45
40
Алгорифм Маркова, заданный в алфавите A = {a} с использованием дополнительного символа * уменьшает количество букв в слове в 2 раза. При этом, если количество букв нечетно, "непарная" буква удаляется, т.е. слово из 5 букв преобразуется в слово из 2 букв.
Z = | *aa → a* | *a →. Λ |
| * →. Λ | Λ → * |
Z = | *aa → Λ | *a → Λ |
| * →. a | Λ → a* |
Z = | *aa →. a* | *a →. Λ |
| * →. Λ | Λ → * |
Z = | *aa → *a | *a →. Λ |
| * →. Λ | Λ → * |
Записать результат применения нормального алгорифма со схемой
Z = |*00 → 0*0 | *01 → 1*0 |
| *10 → 0*1 | *11 → 1*1 |
| * →. Λ | Λ → * |
к слову P = 100110
001101
000111
001110
111000
Какова длина результирующего слова, образующегося после применения к слову abccba нормального алгорифма со схемой
Z = |*a → aa* | *b → bb* |
| *c → cc* | * → Λ |
| #a →. Λ | #b →. Λ |
| #c →. Λ | # →. Λ | Λ → #* |
11
12
1
0
Нормальный алгорифм задан схемой
Z = | *0 → 00* | *1 → 01* |
| *2 → 10* | *3 → 11* |
| * →. Λ | Λ → * |
Определить результат действия алгорифма на слово P=1000
20
01000000
1000000
10
К скольким словам длины 20 применим нормальный алгорифм, заданный в алфавите
A = {a,b}
и описываемый схемой
Z = | ab → ab | ba → ba |
| a→. a | b →. b |
2
220
210
1
Алгорифм Маркова применим к слову, если
алгорифм Маркова завершает свою работу на данном слове за конечное число шагов
хотя бы одна подстановка алгорифма Маркова действует на слово
каждая подстановка алгорифма Маркова действует на слово
каждый символ слова присутствует в левой части какой-либо формулы подстановки алгорифма Маркова
Задан алфавит {a, b, c, d}. В исходном слове Р требуется заменить первое вхождение подслова "bb" на "ddd" и удалить все вхождения символа "c". Какая схема подстановок решает эту задачу?
Z = | bb → ddd | c → Λ |
Z = | bb → ddd | c →. Λ |
Z = | c → Λ | bb → ddd |
Z = | c → Λ | bb → .ddd |
Задан алфавит {a, b, *} и схема подстановок
Z = | *a →. Λ │ *b →. Λ │Λ → *|
Каким будет результат применения НАМ к слову "bbbaba"?
aba
bbaba
bbbaba
******
Что означает запись !α(P)
Нормальный алгорифм Маркова α применим к слову P.
Нормальный алгорифм Маркова α НЕ применим к слову P.
Нормальный алгорифм Маркова α имеет слово P левой части одной из подстановок.
Нормальный алгорифм Маркова α имеет слово P правой части одной из подстановок.
Что означает запись α : P⟹Q
Нормальный алгорифм Маркова α имеет в своей схеме подстановку, левая часть которой равна P, а правая - равна Q.
Нормальный алгорифм Маркова α преобразует P в слово Q.
Нормальный алгорифм Маркова α имеет в своей схеме подстановку, левая часть которой содержит P, а правая - содержит Q.
Нормальный алгорифм Маркова α заканчивает свою работу за конченое число шагов только для слова P, и результат преобразований при этом равен Q.
