Автоматів аналіз
Матеріал з Вікіпедії — вільної енциклопедії.
Автома́тів ана́ліз — знаходження за заданим в тому або іншому вигляді автоматові відображення «вхід — вихід», що здійснюється цим автоматом. Часто таке відображення можна інтерпретувати як обчислення предиката, і оскільки кожен предикат повністю характеризується своїм множиною істинності, то завдання аналізу автомата зводиться до знаходження цієї множини (говорять, що ця множина розпізнається автоматом). Для багатьох класів автоматів добре відомі класи розпізнаваних ними множин. Напр., Т'юрінга машини розпізнають всі рекурсивні зліченні множини, автомати з магазинною пам'яттю (недетерміновані) — контекстні вільні мови, автомати кінцеві — події, регулярні. Далеко не завжди по заданих автомату і множині вдається визначити, чи розпізнає автомат в точності цю множину.
У загальному вигляді для довільного класу автоматів або навіть для довільного конкретного автомата ця проблема є алгоритмічно нерозв'язною. Якщо накласти обмеження на способи завдання автоматів і на способи завдання множин, то для багатьох випадків вона стає вирішуваною. Напр., якщо регулярні події задавати регулярними виразами, а кінцеві автомати — матрицями переходів і виходів, то існує загальний конструктивний прийом (алгоритм аналізу кінцевих автоматів), що дозволяє знаходити регулярні вирази для подій, уявних в довільному кінцевому автоматі.
[ред.] Література
- Енциклопедія кібернетики
- Глушков В. М. Синтез цифровых автоматов. М., 1962 [библиогр. с. 464—469].
М. І. Кратко.