Тест "Нормальные алгоритмы Маркова"
тест на тему

Тест «Нормальные алгоритмы Маркова» 1 вариант

1. Результат марковской подстановки 21  3 в слово 521421

a) 52143                b) 5343

c) 531421                d) 533433

2. Марковская подстановка 21  3 не применима к словам

a) 521421        b) 5241

c) 21                d)12

3. Результат марковской подстановки 21   в слово 521421

a) 54                b)21521421

c) 5421        d)52142121

4. Слово 21 является подсловом слова

a) 521421        b) 5241

c) 521                d) 2541

5. Процесс работы нормального алгоритма считается завершенным, если на данном шаге

1. Применена последняя формула в списке формул марковских подстановок, задающих данный алгоритм
2. Применена заключительная формула подстановки
3. Ни одна подстановка схемы не подходит
4. Понятно, что процесс подстановок не сможет остановиться

6. Нормальный алгоритм не применим к исходным данным, если на данном шаге

1. Применена последняя формула в списке формул марковских подстановок, задающих данный алгоритм
2. Применена заключительная формула подстановки
3. Ни одна подстановка схемы не подходит
4. Понятно, что процесс подстановок не сможет остановиться

7. Каким будет результат применения нормального алгоритма ab ® L, ba ® ab к слову R = bbaabab 

8. Результат применения нормального алгоритма ab ® bd, db ® ba, bba ® abb, c ® L к слову R = abbc

1. Алгоритм не применим к этому слову
2. bb
3. aa
4. cc

9. В алгоритме Маркова ассоциативным исчислением называется:

1. совокупность всех слов в данном алфавите;
2. совокупность всех допустимых систем подстановок;
3. совокупность всех слов в данном алфавите вместе с допустимой системой подстановок;
4. когда все слова в алфавите являются смежными.

10. В ассоциативном счислении два слова называются смежными:

1. если одно из них может быть преобразовано в другое применением подстановок;
2. если одно из них может быть преобразовано в другое однократным применением допустимой подстановки;
3. когда существует цепочка от одного слова к другому и обратно;
4. когда они дедуктивны.

11. В алгоритмах Маркова дана система подстановок в алфавите
    A = {а, b, с}:  abc — с;        ba — cb;        ca — ab

Преобразуйте с помощью этой системы слово bacaabc

12. В алгоритмах Маркова дана система подстановок в алфавите
    А= {а, b, с}:cb — abc;        bас — ас; cab — b

Преобразуйте с помощью этой системы слово bcabacab

13. Способ композиции нормальных алгоритмов будет суперпозицией, если:

1. выходное слово первого алгоритма является входным для второго;
2. существует алгоритм С, преобразующий любое слово р, содержащееся I пересечении областей определения алгоритмов А и В;
3. алгоритм D будет суперпозицией трех алгоритмов ABC, причем область определения D является пересечением областей определения алгоритмов А В и С, а для любого слова р из этого пересечения D(p) = А(р), если С(р) = е, D(p) = В(р), если С(р) = е, где е — пустая строка;
4. существует алгоритм С, являющийся суперпозицией алгоритмов А и Д такой, что для любого входного слова р С(р) получается в результате последовательного многократного применения алгоритма А до тех пор, пока не получится слово, преобразуемое алгоритмом В.

14. Способ композиции нормальных алгоритмов будет объединением, если:

1. выходное слово первого алгоритма является входным для второго;
2. существует алгоритм С, преобразующий любое слово р, содержащееся в пересечении областей определения алгоритмов А и В;
3. алгоритм В будет суперпозицией трех алгоритмов ABC, причем область определения D является пересечением областей определения алгоритмов А В и С, а для любого слова р из этого пересечения D(p) — A(p), если С(р) = е, D(p) = В(р), если С(р) = е, где е — пустая строка;
4. существует алгоритм С, являющийся суперпозицией алгоритмов А и Д такой, что для любого входного слова р С(р) получается в результате последовательного многократного применения алгоритма А до тех пор, пока не получится слово, преобразуемое алгоритмом В.

15. Способ композиции нормальных алгоритмов будет разветвлением, если:

1. выходное слово первого алгоритма является входным для второго;
2. существует алгоритм С, преобразующий любое слово р, содержащееся в пересечении областей определения алгоритмов А и В;
3. алгоритм D будет суперпозицией трех алгоритмов ABC, причем область определения D является пересечением областей определения алгоритмов А В и С, а для любого слова р из этого пересечения D(p) = А(р), если С(р) = е, D(p) – В(р), если С(р) = е, где е — пустая строка;
4. существует алгоритм С, являющийся суперпозицией алгоритмов А и В, такой, что для любого входного слова р С(р) получается в результате последовательного многократного применения алгоритма А до тех пор, пока не получится слово, преобразуемое алгоритмом В.

16. Способ композиции нормальных алгоритмов будет итерацией, если:

1. выходное слово первого алгоритма является входным для второго;
2. существует алгоритм С, преобразующий любое слово р, содержащееся в пересечении областей определения алгоритмов А и В;
3. алгоритм D будет суперпозицией трех алгоритмов ABC, причем область определения D является пересечением областей определения алгоритмов А В к С, а для любого слова р из этого пересечения D(p)= A(p), если С(р) = е, D(p) — В(р), если С(р) = е, где е — пустая строка;
4. существует алгоритм С, являющийся суперпозицией алгоритмов А и В, такой, что для любого входного слова р С(р) получается в результате последовательного многократного применения алгоритма А до тех пор, пока не получится слово, преобразуемое алгоритмом В.

17. Дать подробное решение и описание алгоритма решения задачи:

1. A={f,h,p} в слове P заменить все пары ph на f
2. A={a,b,c} Приписать слово bac слева к слову P

Тест «Нормальные алгоритмы Маркова» 2 вариант

1. Каким будет результат применения нормального алгоритма ab ® L, ba ® ab к слову R = bbaabab 

2. Слово 21 является подсловом слова

a) 521421        b) 5241

c) 521                d) 2541

3. Нормальный алгоритм не применим к исходным данным, если на данном шаге

1. Применена последняя формула в списке формул марковских подстановок, задающих данный алгоритм
2. Применена заключительная формула подстановки
3. Ни одна подстановка схемы не подходит
4. Понятно, что процесс подстановок не сможет остановиться

4. В алгоритмах Маркова дана система подстановок в алфавите
   А= {а, b, с}:cb — abc;        bас — ас; cab — b

Преобразуйте с помощью этой системы слово bcabacab

5. Способ композиции нормальных алгоритмов будет итерацией, если:

1. выходное слово первого алгоритма является входным для второго;
2. существует алгоритм С, преобразующий любое слово р, содержащееся в пересечении областей определения алгоритмов А и В;
3. алгоритм D будет суперпозицией трех алгоритмов ABC, причем область определения D является пересечением областей определения алгоритмов А В к С, а для любого слова р из этого пересечения D(p)= A(p), если С(р) = е, D(p) — В(р), если С(р) = е, где е — пустая строка;
4. существует алгоритм С, являющийся суперпозицией алгоритмов А и В, такой, что для любого входного слова р С(р) получается в результате последовательного многократного применения алгоритма А до тех пор, пока не получится слово, преобразуемое алгоритмом В.

6. Способ композиции нормальных алгоритмов будет объединением, если:

1. выходное слово первого алгоритма является входным для второго;
2. существует алгоритм С, преобразующий любое слово р, содержащееся в пересечении областей определения алгоритмов А и В;
3. алгоритм В будет суперпозицией трех алгоритмов ABC, причем область определения D является пересечением областей определения алгоритмов А В и С, а для любого слова р из этого пересечения D(p) — A(p), если С(р) = е, D(p) = В(р), если С(р) = е, где е — пустая строка;
4. существует алгоритм С, являющийся суперпозицией алгоритмов А и Д такой, что для любого входного слова р С(р) получается в результате последовательного многократного применения алгоритма А до тех пор, пока не получится слово, преобразуемое алгоритмом В.

7. Способ композиции нормальных алгоритмов будет суперпозицией, если:

1. выходное слово первого алгоритма является входным для второго;
2. существует алгоритм С, преобразующий любое слово р, содержащееся I пересечении областей определения алгоритмов А и В;
3. алгоритм D будет суперпозицией трех алгоритмов ABC, причем область определения D является пересечением областей определения алгоритмов А В и С, а для любого слова р из этого пересечения D(p) = А(р), если С(р) = е, D(p) = В(р), если С(р) = е, где е — пустая строка;
4. существует алгоритм С, являющийся суперпозицией алгоритмов А и Д такой, что для любого входного слова р С(р) получается в результате последовательного многократного применения алгоритма А до тех пор, пока не получится слово, преобразуемое алгоритмом В.

8. Способ композиции нормальных алгоритмов будет разветвлением, если:

1. выходное слово первого алгоритма является входным для второго;
2. существует алгоритм С, преобразующий любое слово р, содержащееся в пересечении областей определения алгоритмов А и В;
3. алгоритм D будет суперпозицией трех алгоритмов ABC, причем область определения D является пересечением областей определения алгоритмов А В и С, а для любого слова р из этого пересечения D(p) = А(р), если С(р) = е, D(p) – В(р), если С(р) = е, где е — пустая строка;
4. существует алгоритм С, являющийся суперпозицией алгоритмов А и В, такой, что для любого входного слова р С(р) получается в результате последовательного многократного применения алгоритма А до тех пор, пока не получится слово, преобразуемое алгоритмом В.

9. Процесс работы нормального алгоритма считается завершенным, если на данном шаге

1. Применена последняя формула в списке формул марковских подстановок, задающих данный алгоритм
2. Применена заключительная формула подстановки
3. Ни одна подстановка схемы не подходит
4. Понятно, что процесс подстановок не сможет остановиться

10. Результат марковской подстановки 21  3 в слово 521421

a) 52143                b) 5343

c) 531421                d) 533433

11. Результат применения нормального алгоритма ab ® bd, db ® ba, bba ® abb, c ® L к слову R = abbc

5. Алгоритм не применим к этому слову
6. bb
7. aa
8. cc

12. В алгоритмах Маркова дана система подстановок в алфавите
    A = {а, b, с}:  abc — с;        ba — cb;        ca — ab

Преобразуйте с помощью этой системы слово bacaabc

13. алгоритме Маркова ассоциативным исчислением называется:

5. совокупность всех слов в данном алфавите;
6. совокупность всех допустимых систем подстановок;
7. совокупность всех слов в данном алфавите вместе с допустимой системой подстановок;
8. когда все слова в алфавите являются смежными.

14. В ассоциативном счислении два слова называются смежными:

5. если одно из них может быть преобразовано в другое применением подстановок;
6. если одно из них может быть преобразовано в другое однократным применением допустимой подстановки;
7. когда существует цепочка от одного слова к другому и обратно;
8. когда они дедуктивны.

15. Марковская подстановка 21  3 не применима к словам

a) 521421        b) 5241

c) 21                d)12

16. Результат марковской подстановки 21   в слово 521421

a) 54                b)21521421

c) 5421        d)52142121

17. Дать подробное решение и описание алгоритма решения задачи:

3. A={a,b,c} в слове P заменить все пары ac на b
4. A={p,f} Приписать слово fpf слева к слову S