Лабораторна робота №3 «Застосування нормальних алгоритмів Маркова»

Лабораторна робота №3
«Застосування нормальних алгоритмів Маркова»
1.Тема: Застосування нормальних алгоритмів Маркова.

2.Опис робочого місця :
2.1. Комп'ютер.

3.Тривалість роботи: Приблизно 180 хвилин.

4.Мета роботи: навчитися складати нормальні алгоритми Маркова.
Завдання по варіантах.

5.Зміст і послідовність виконання роботи :

До кожного завдання записати алфавіт, розробити нормальний алгоритм Маркова у вигляді системи формул, зробити покровів прогін для (кілька прикладів), реалізувати НАМ у програмі, зробити скриншоти результатів, зробити висновки.

Варіант 1.

Завдання 1

Дан алфавіт A=(c,d,e,f). Символи у вхідному слові відсортувати по алфавіту.

Завдання 2

Дан алфавіт A=(k,l,m,n). Всі літери m і n замінити порожнім символом, перше входження ll замінити на nnn.

Варіант 2.

Завдання 1

Дан алфавіт A=(o,p,q,r ). Символи у вхідному слові відсортувати по алфавіту.

Завдання 2

Дан алфавіт A=(c,d,e,f). Всі літери c і d замінити порожнім символом, перше входження f замінити на ee.

Варіант 3.

Завдання 1

Дан алфавіт A=(e,f,g,h). Символи у вхідному слові відсортувати по алфавіту.

Завдання 2

Дан алфавіт A=(a,b,c,d). Всі літери c і d замінити порожнім символом, перше входження aa замінити на bbb.

Варіант 4.

Завдання 1

Дан алфавіт A=(x,y,z,w). Символи у вхідному слові відсортувати по алфавіту.

Завдання 2

Дан алфавіт A=(o,s,q,r). Всі літери o і s замінити порожнім символом, перше входження qq замінити на rr.

Варіант 5.

Завдання 1

Дан алфавіт A=(t,r,e,c). Символи у вхідному слові відсортувати по алфавіту.

Завдання 2

Дан алфавіт A=(g,t,b,n). Всі літери g і t замінити порожнім символом, перше входження b замінити на nn.

Варіант 6.

Завдання 1

Дан алфавіт A=(s,q,n,d). Символи у вхідному слові відсортувати по алфавіту.

Завдання 2

Дан алфавіт A=(a,b,c,d). Всі літери c і d замінити порожнім символом, перше входження c замінити на dd.

Дати відповіді на контрольні питання.

1. У чому різниця між НАМ і машиною Тьюринга? ?
2. Коли зупиняється робота НАМ?
3. Для чого використовується спецзнак?
4. Яка різниця між кінцевою і звичайною формулами?