заданому абстрактного автомата Мілі або Мура А знайти відповідне йому канонічне безліч подій М,
) по заданому автоматного безлічі подій М знайти абстрактний автомат Мілі або Мура А, канонічне безліч подій якого збігається з М.
Одне і те ж подія допускає кілька еквівалентних форм регулярних виразів. Тому в результаті аналізу потрібно відшукати регулярне вираз, має мінімальну циклічну глибину. p align="justify"> Канонічна задача синтезу автоматів по своїй суті неоднозначна. Це пояснюється тим, що абстрактний автомат не визначається однозначно відповідним йому канонічним безліччю подій, оскільки одне і те ж автоматне відображення може індукувати різними абстрактними автоматами. Тому в результаті рішення канонічної задачі синтезу знаходимо один з можливих автоматів, а потім ставиться завдання мінімізації абстрактних автоматів, яка полягає у знаходженні автомата з мінімальним числом станів. p align="justify"> Загальні завдання аналізу та синтезу автоматів формулюються таким чином:
) по заданому абстрактного автомата Мілі або Мура А знайти подія, яке представлене в автоматі А будь-яким безліччю вихідних букв або стані автомата;
) з будь-якого кінцевого безлічі подій побудувати абстрактний автомат Мілі або Мура А. який представляє кожну подію цієї множини деяким безліччю вихідних букв або станів.
Існує стандартний прийом відомості обший задачі синтезу автоматів до канонічної задачі синтезу, яка завжди має рішення, заснований на наступному твердженні.
3. Малюнки автоматів
S0
a/x
S1
b/y
В
S2
a/x
b/y
a/x
S3
В
a/x
S4
S0 - залізничний роз'їзд-перший шлях-другий шлях-третій шлях-пункт призначення
а/г - вільний, їдемо безпосередньо/y - зайнятий, встаємо на наступний шлях
Рисунок 1 - Автомат Міллі
? аbS0S1-S1S4S2S2S4S3S3S4-S4 -
? аbS0х-S1хуS2хуS3х-S4 -
S0
a
S1/г
b
В
S2/у
a
b
a
S3/у
В
a
S4/г
- залізничний роз'їзд/г - перш...
