Теорія алгоритмів. Задача Приведіть графсхему узагальненого алгоритму Маркова в алфавіті a,b,c та визначте кінцеве слово за вхідним словом bbaccaab та системою підстановок abba, cac.

• Название: Задача Приведіть графсхему узагальненого алгоритму Маркова в алфавіті a,b,c та визначте кінцеве слово за вхідним словом bbaccaab та системою підстановок abba, cac.
• Дата: 27.06.2018
• Размер: 81.41 Kb.
• Имя файла: Теорія алгоритмів.docx
• Тип: Задача; #47999

Задача 4. Приведіть граф-схему узагальненого алгоритму Маркова в алфавіті {a,b,c} та визначте кінцеве слово за вхідним словом bbaccaab та системою підстановок {ab->ba, ca->c}.

ab

ca

ab → ba

ca→c

вхід

p

вихід

p = bbaccaab → bbaccaba→ bbaccbaa

Вихідне слово: bbaccbaa

Задача 5. Приведіть граф-схему нормального алгоритму Маркова в алфавіті {0,1} та визначте кінцеве слово за вхідним словом 011100101 та системою підстановок {11->01, 10->1, 1->•е}.

вхід

10

11

1

11→01

10→1

1→•e

p

Вихід

011100101→001100101→000100101→00010101→0001101→0000101→ 000011→000001→00000•е

Задача 8. Приведіть граф, що відповідає автомату 1 роду (Mealy machine), поданому таблицею переходів та таблицею виходів, і за вхідним словом xxxyyxz визначте кінцеве слово.

Таблиця переходів
	1	2	3	4
x	3	1	1	3
y	3	2	1	4
z	3	3	2	1

Таблиця виходів
	1	2	3	4
x	u	v	w	u
y	v	w	v	v
z	w	u	u	v

Автомат знаходиться в стані 1.

1. 
   Стан 1, вх. сигнал х → Стан 3;
   
2. 
   Стан 1, вх. сигнал х → вих.сигнал u;
   
3. 
   Стан 3, вх. сигнал х → Стан 1;
   
4. 
   Стан 3, вх. сигнал х → вих.сигнал w;
   
5. 
   Стан 1, вх. сигнал х → Стан 3;
   
6. 
   Стан 1, вх. сигнал х → вих.сигнал u;
   
7. 
   Стан 3, вх. сигнал y → Стан 1; Вихідне слово: uwuvvww
   
8. 
   Стан 3, вх. сигнал y → вих.сигнал v;
   
9. 
   Стан 1, вх. сигнал y → Стан 3;
   
10. 
    Стан 1, вх. сигнал y → вих.сигнал v;
    
11. 
    Стан 3, вх. сигнал х → Стан 1;
    
12. 
    Стан 3, вх. сигнал х → вих.сигнал w;
    
13. 
    Стан 1, вх. сигнал z → Стан 3;
    
14. 
    Стан 1, вх. сигнал z → вих.сигнал w;
    

	p	u	r
	1	2	3
a	1	1	2
b	3	2	1
c	1	3	2
d	3	2	1

Задача 9. Приведіть граф, що відповідає автомату 2 роду (Moore machine), поданому приведеною таблицею виходів. За вхідним словом ababccddab визначте кінцеве слово.

Автомат знаходиться в стані 1.

1. 
   Стан 1, вх. сигнал a → стан 1, вих. сигнал p;
   
2. 
   Стан 1, вх. сигнал b → стан 3, вих. сигнал r;
   
3. 
   Стан 3, вх. сигнал a → стан 2, вих. сигнал u;
   
4. 
   Стан 2, вх. сигнал b → стан 2, вих. сигнал u;
   
5. 
   Стан 2, вх. сигнал c → стан 3, вих. сигнал r;
   
6. 
   Стан 3, вх. сигнал c → стан 2, вих. сигнал u;
   
7. 
   Стан 2, вх. сигнал d → стан 2, вих. сигнал u;
   
8. 
   Стан 2, вх. сигнал d → стан 2, вих. сигнал u;
   
9. 
   Стан 2, вх. сигнал a → стан 1, вих. сигнал p;
   
10. 
    Стан 1, вх. сигнал b → стан 3, вих. сигнал r;
    

Вихідне слово: pruuruuupr