Аналіз автоматів

Автома́тів ана́ліз — знаходження за заданим в тому або іншому вигляді автоматові відображення «вхід — вихід», що здійснюється цим автоматом. Часто таке відображення можна інтерпретувати як обчислення предиката, і оскільки кожен предикат повністю характеризується своїм множиною істинності, то завдання аналізу автомата зводиться до знаходження цієї множини (говорять, що ця множина розпізнається автоматом). Для багатьох класів автоматів добре відомі класи розпізнаваних ними множин. Наприклад, машина Тюрінга розпізнає всі рекурсивні зліченні множини, автомат з магазинною пам'яттю (недетермінований) — контекстні вільні мови, скінченний автомат — регулярні події.

Далеко не завжди по заданих автомату і множині вдається визначити, чи розпізнає автомат в точності цю множину.

У загальному вигляді для довільного класу автоматів або навіть для довільного конкретного автомата ця проблема є алгоритмічно нерозв'язною. Якщо накласти обмеження на способи завдання автоматів і на способи завдання множин, то для багатьох випадків вона стає вирішуваною. Наприклад, якщо регулярні події задавати регулярними виразами, а скінченні автомати — матрицями переходів і виходів, то існує загальний конструктивний прийом (алгоритм аналізу скінченних автоматів), що дозволяє знаходити регулярні вирази для подій, уявних в довільному скінченному автоматі.

Література

• Енциклопедія кібернетики : у 2 т. / за ред. В. М. Глушкова. — Київ : Гол. ред. Української радянської енциклопедії, 1973., М. І. Кратко.
• Глушков В. М. Синтез цифровых автоматов. М., 1962 [библиогр. с. 464—469].