ості, на малюнку не зображено стан Lі ведуть до нього переходи. <В
Рис. 4
7. Побудова мережі Петрі
Побудуємо для граматики G 'мережа Петрі. Для цього, поставимо у відповідність нетермінальним символам позиції (гуртки) мережі. А терміналам - переходи (планки) мережі. Пометим позиції і переходи відповідними нетерміналами і терміналами. p align="justify"> Позиції з'єднуються дугами тільки через переходи, а переходи - через позиції. Якщо в правій частині деякого правило виведення з R має місце конкатенація терміналів, то в мережі Петрі між переходами, поміченими терміналами, повинні з'являтися додаткові позиції, які можна позначати символами лівій частині правил виводу з індексами 1, 2 , ....
Таким чином, позиції можуть мати кілька вхідних і вихідних дуг, але переходи - в точності за однією вхідної та не більше ніж однієї вихідної дузі (що виходить дуга може бути відсутнім, якщо в правій частині правила виведення відсутня замикає нетермінал ).
Виконавши ці дії, отримуємо мережу Петрі (рис. 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"> недетермінірованность усувається склеюванням двох позицій P l і P k в одну (P l , P k ). При цьому позиції (P l , P k < span align = "justify">) інцидентні всі вихідні дуги, які є вихідним...
