Рассматривается формализм, предназначенный для представления
специального расширения класса конечных автоматов – так называемых
обобщенных недетерминированных конечных автоматов. <...> Из изложенных
в статье алгоритмов эквивалентного преобразования определяемых нами автоматов и аналога теоремы Клини для них вытекает не столько эквивалентность их и обычных конечных автоматов (эта эквивалентность очевидна априори), сколько возможность определения операции дополнения (и вообще
обобщенных регулярных выражений) обычными «автоматными» методами. <...> Также в статье описан метод построения конкретного обобщенного автомата,
который определяет заданное обобщенное регулярное выражение. <...> Данный
метод вытекает из доказательства аналога теоремы Клини. <...> Представленные
расширенные возможности для описания регулярных языков могут быть полезны в некоторых приложениях, например, в контекстном поиске. <...> Ключевые слова: недетерминированные конечные автоматы, обобщенные регулярные выражения, алгоритмы эквивалентного преобразования, аналог теоремы Клини. <...> The article considers the formalism used for representing a special class of
extensions of finite automata, so-called generalized indeterministic finite automata. <...> The described algorithms of equivalent transformations of such automata and also
their analogue of Kleene theorem result in not only the equivalence between such
and usual finite automata (such equivalence is obvious a priori), but also in the possibility of defining the complement operation (and, generally, the generalized regular expressions) by usual “automata” methods. <...> Key words: indeterministic finite automaton, generalized regular expressions, algorithms of equivalent transformation, analogue of Kleene theorem. <...> Введение
В данной статье рассматривается формализм, предназначенный для
представления специального расширения класса недетерминированных конечных автоматов. <...> При этом, кроме более подробного изложения рассмотренных в [1–3] понятий и доказанных фактов, в настоящей статье также
описывается метод построения конкретного обобщенного автомата, который
определяет (среди прочих) заданное обобщенное регулярное выражение. <...> Этот метод построения фактически завершает описание рассматриваемого <...>