Обобщенные недетерминированные конечные автоматы

Рассматривается формализм, предназначенный для представления специального расширения класса конечных автоматов - так называемых обобщенных недетерминированных конечных автоматов. Из изложенных в статье алгоритмов эквивалентного преобразования определяемых авторами автоматов и аналога теоремы Клини для них вытекает не столько эквивалентность их и обычных конечных автоматов (эта эквивалентность очевидна априори), сколько возможность определения операции дополнения (и вообще обобщенных регулярных выражений) обычными "автоматными" методами. Также в статье описан метод построения конкретного обобщенного автомата, который определяет заданное обобщенное регулярное выражение. Данный метод вытекает из доказательства аналога теоремы Клини. Представленные расширенные возможности для описания регулярных языков могут быть полезны в некоторых приложениях, например, в контекстном поиске.

Вы можете купить электронную версию издания «Обобщенные недетерминированные конечные автоматы». После оплаты (для архивов) оно будет доступно в Личном Кабинете в разделе «Электронные издания». В случае оформления подписки, издание будет доступно по мере поступления от издателя. Формат PDF/HTML. Стоимость — от 90.00 руб.