АВТОМАТОВ АНАЛИЗ

— нахождение по заданному в том или ином виде автомату отображения «вход — выход», осуществляемого этим автоматом. Часто такое отображение можно интерпретировать как вычисление предиката, и поскольку каждый предикат полностью характеризуется своим мн-вом истинности, то задача анализа автомата сводится к нахождению этого мн-ва (говорят, что это мн-во распознается автоматом). Для многих классов автоматов хорошо известны классы распознаваемых ими множеств. Наир., Тьюринга машины распознают все рекурсивно перечислимые мн-ва, автоматы с магазинной памятью (недетерминированные) — контекстно свободные языки, автоматы конечные — события, регулярные. Далеко не всегда по заданным автомату и мн-ву удается определить, распознает ли автомат в точности это мн-во. В общем виде для произвольного класса автоматов или даже для произвольного конкретного автомата эта проблема является алгоритмически неразрешимой. Если наложить ограничения на способы задания автоматов и на способы задания множеств, то для многих случаев она становится разрешимой. Напр., если регулярные события задавать регулярными выражениями, а конечные автоматы — матрицами переходов и выходов, то существует общий конструктивный прием (алгоритм анализа конечных автоматов), позволяющий находить регулярные выражения для событий, представимых в произвольном конечном автомате.

Лит.: Глушков В. М. Синтез цифровых автоматов. М., 1962 [библиогр. с. 464—469].

М. И. Кратко.