ДОКАЗАТЕЛЬСТВА СОВПАДЕНИЯ АВТОМАТОВ COM И УНИВЕРСАЛЬНОГО

Авторы

  • Василий Николаевич Долгов Тольяттинский государственный университет
  • Мария Анатольевна Зубова Тольяттинский государственный университет

Ключевые слова:

универсальный автомат Конвея, множество возможных дуг

Аннотация

В статье представлены 2 разных доказательства совпадения универсального автомата Конвея и автомата COM, определяющегося через множество всевозможных дуг всех автоматов для заданного регулярного языка.

Библиографические ссылки

1. Conway, J.H. Regular Algebra and Finite Machines / J. H. Conway – L: Chapman and Hall, 1971. – 147 p.
2. Melnikov, B. Extended nondeterministic finite automata / B. Melnikov // Fundamenta Informaticae. – Vol.104 (2010) No.3. – P. 255–265.
3. Мельников, Б.Ф. Недетерминированные конечные автоматы: монография / Б.Ф. Мельников – Тольятти: Изд-во ТГУ, 2009. – 160 с.
4. Лаллеман, Ж. Полугруппы и комбинаторные приложения: пер. с англ. / Ж. Лаллеман. – М.: Мир, 1985. – 440 с.
5. Lombardy, S., Sakarovitch, J. The Universal Automaton / S. Lombardy, J. Sakarovitch // Logic and Automata, Texts in Logic and Games, Vol. 2, Amsterdam Univ. Press. – Amsterdam, 2008. – P. 457–504.
6. Мельников, Б.Ф. Построение автомата COM на основе базисного автомата / Б.Ф. Мельников, М.А. Зубова // Вектор науки Тольяттинского государственного университета. – Тольятти, 2010. – № 4 (14). – С. 30–32.
7. 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 (2002) No.2. – P. 475–485.
8. Carrez, C. On the minimalization of non-deterministic automaton: technical report / C. Carrez. – Computing Laboratory of the Science Faculty of Lille University, 1970.
9. Melnikov, B. Once more on the edge-minimization of nondeterministic finite automata and the connected problems / B. Melnikov // Fundamenta Informaticae. – Vol.104 (2010) No.3. – P. 267–283.

Загрузки

Выпуск

Раздел

Естественные науки