45. Структури і типи даних для визначення графів-автоматів.

Ос­но­ву найпростішої програмної реалізації скінченного авто­мату складають коди стану автомата та так звана матриця пере­хо­дів автомата. Коди стану, частіше за все, визначаються перену­ме­ро­ваним типом з іменованими значеннями станів. Приклад опису типу для подання автомата з 5-ма станами, наведеного на рис. 3.7 показано нижче. Дуги та назви сигналів, за якими зберігається попередній стан графа на схемі умовно не показані.

Fig. 8.7. Стани кінцевого автомата

enum autStat

{S0, // S₀ - Початковий стан

S1, // S₁ - Перший стан

S2, // S₂ - Другий стан

Se // S_e - Останній стан

};

Коди сигналів також зручно визначати іншим перену­ме­ро­ваним типом з іменованими значеннями кодів сигналів. Приклад опису типу для подання 5 типів сигналів, показаного на рис. 3.7, наведено нижче.

enum autSgn

{sg0, // s₀ - Початковий сигнал

sg1, // s₁ - Перший сигнал

sg2, // s₂ - Другий сигнал

sg3, // s₃ - Третій сигнал

sgE // s_E - Заключний сигнал

};

Матриця переходів визначається двомірним масивом типу enum autStat, перший індекс якого визначає ціле число, яке відповідає попередньому стану автомата, а другий індекс – число, яке відповідає сигналу ао класу сигналу для переведення автомата в наступний стан.

enum autStat nxtSts[Se+1][ sgE+1] ={{S0,S1,S2,S0,S0}, // для S0 {S1,S1,S3,S2,Se}, // для S1 {S1,S2,S2,S2,S2}, // для S2 {S1,S3,S3,S2,S2}, // для S3 {Se,Se,Se,Se,Se} // для Se};

Функція переходів визначена в лабораторній роботі наступним чином:

enum autStat nxtStat(enum autSgn sgn)

{static enum autStat s=S0;// поточний стан лексеми

return s=nxtSts[s][sgn]; // новий стан лексеми

}

46. Декомпозиція задач на послідовні блоки. 47. Декомпозиція задач на паралельно-виконувані блоки. 48. Декомпозиція задач на розгалуджувані блоки. 49. Декомпозиція задач обробки масивів на циклічні блоки. 50. Декомпозиція задач обробки рекурсивних математичних формул. 51. Особливості обробки термінальних вузлів дерев підлеглості. 52. Особливості обробки нетермінальних вузлів дерев підлеглості операцій. 53. Особливості обробки присвоювань в деревах підлеглості операцій. 54. Особливості обробки тернарних операцій в деревах підлеглості операцій. 55. Способи виявлення та локалізації помилок в розпаралелених програмах. 56. Способи виявлення та локалізації помилок в лінійних програмах. 57. Способи виявлення та локалізації помилок в розгалуджених програмах. 58. Способи виявлення та локалізації помилок в циклічних програмах. 59. Способи корекції помилок в розпаралелених програмах. 60. Способи корекції помилок в лінійних програмах. 61. Способи корекції помилок в розгалуджених програмах. 62. Способи корекції помилок в циклічних програмах.