вихідної дузі (що виходить дуга може бути відсутнім, якщо в правій частині правила виведення відсутня замикає нетермінал ).
Виконавши ці дії, отримуємо мережу Петрі (рис. 5).
Мережа Петрі
В
Рис. 5
Для повноти відповідності побудованої мережі Петрі розпізнавального автомату Мура, введені не показану на рис. 5 заключну позицію Z, в яку направимо дуги з усіх переходів, раніше не мали вихідних дуг. У результаті одержимо нову мережу Петрі (рис. 6). br/>
Мережа Петрі з заключній позицією Z
В
Рис. 6
Далі, необхідно мінімізувати мережа Петрі. Для цього визначимо в ній ідентичні фрагменти. Отже, ідентичними фрагментами є позиції D і E c інцидентними їм переходами x5 і x4. Також, позиції A, B і С з інцидентними їм переходами x4 і x7. Позиції S1 і S3, F2 і F5, F3 і F6, F1 і F4, F6 і F8 можна склеїти попарно. В результаті отримуємо мінімізовану недетермінірованного мережа Петрі (рис. 7). br/>
мінімізували мережа Петрі
В
Рис. 7
Цей етап відповідає мінімізації кількості станів автомата, але він виконаний для автомата, що зберігає недетермінірованность. Джерелом недетермінованости, очевидно, можуть бути лише позиції вільного вибору, вихідні дуги яких є вхідними дугами переходів, помічених однаковими терміналами. p align="justify"> недетермінірованность усувається склеюванням двох позицій Pl і Pk в одну (Pl, Pk). При цьому позиції (Pl, Pk) інцидентні всі вихідні дуги, які є вихідними дугами позицій Pl і Pk. p align="justify"> В отриманій мережі Петрі відсутні позиції вільного вибору, вихідні дуги яких є вхідними дугами переходів, помічених однаковими терміналами. А значить, мережа Петрі (рис. 7) вже детермінована і мінімізована. br/>
Тепер позначимо позиції мережі Петрі наступними літерами:
S -> A S1, S3 -> BF -> C F7 -> D F2, F5 -> E F1, F4 -> FS2, S4 -> GD, E -> HA, B, C -> I F3, F6, F8 -> JZ -> K
Приберемо переходи з мережі Петрі, дуги підпишемо терміналами переходів, тоді отримаємо граф переходів (рис.8).
Граф переходів отриманий з мережі Петрі
В
Рис.8
Порівнявши отриманий граф (рис.8) з графом мінімального автомата (мал. 4) ми бачимо, що вони ідентичні. Значить, мінімальний автомат побудований правильно. p align="justify"> 8. ОПИС програми, що реалізують розпізнала АВТОМАТ
8.1 Вступна частина
Програма: машина Тьюринга
Позначення програми: turing.exe
Програма використовується для побудови моделей машини Тьюринга
8.2 Функціональне призначення
Програма призначена...
