ПОСТРОЕНИЕ АВТОМАТА COM НА ОСНОВЕ БАЗИСНОГО АВТОМАТА

  • Борис Феликсович Мельников Тольяттинский государственный университет
  • Мария Анатольевна Зубова Тольяттинский государственный университет
Ключевые слова: недетерминированный конечный автомат, базисный автомат, множество всевозможных дуг

Аннотация

В статье рассматривается множество дуг, определённое на блоках бинарного отношения #. Дуги этого множества соответствуют всем возможным дугам любого недетерминированного конечного автомата, определяющего заданный регулярный язык. На основе этого множества дуг определяется автомат COM, являющийся инвариантом рассматриваемого языка. В статье получены описания входных и выходных языков состояний автомата COM.

Литература

Melnikov B. A new algorithm of constructing the basis finite automaton
/ B.Melnikov, A.Melnikova – Informatika (Lithuanian Acad. Sci. Ed.), Vol.13, No.3 (2002) 299–310.
2. Мельников Б.Ф. Недетерминированные конечные автоматы
/ Б.Ф. Мельников – Тольятти: Изд-во ТГУ. – 2009. – 160 с.
3. Зузанова М.Р. Некоторые алгоритмы эквивалентного преобразования недетерминированных конечных автоматов: дис. …канд. физ.-мат. наук : 05.13.18 / М.Р.Зузанова – Тольятти: ТГУ, 2010. – 115 с.
4. Lombardy S. Star height of reversible languages and universal automata
/ S.Lombardy, J.Sakarovitch – In: LATIN 2002: Theoretical informatics (Cancun), volume 2286 of Lecture Notes in Comput. Sci., pages 76–90, Berlin, 2002.
5. Melnikov B. Possible edges of a finite automaton defining a given regular language / B.Melnikov, N.Sciarini-Guryanova – The Korean J. Comp. and Appl. Math., Vol.9, No.2 (2002) 475–485.
6. Polák L. Minimalizations of NFA using the universal automaton
/ L. Polák – Int. J. Found.Comput. Sci., Vol. 16, No. 5 (2005) 999–1010.
7. Melnikov B. On an expansion of nondeterministic finite automata
/ B.Melnikov – J. of Applied Mathematics and Computing, Springer Berlin/Heidelberg, Vol.24, No.1–2 (2007) 155–165.
Выпуск
Раздел
Естественные науки

Наиболее читаемые статьи этого автора (авторов)