Некоторые алгоритмы эквивалентного преобразования недетерминированных конечных автоматов

Актуальность темы

Ещё примерно с начала 1970;х годов в научных публикациях нередко стало прослеживаться мнение, что в теории регулярных языков и конечных автоматов уже решены практически все возможные задачи. Но впоследствии, с началом применения данной теории к различным вопросам нз смежных наук, стало ясно, что для многих задач важен не только сам исследуемый регулярный язык, но и способ, которым он заг даётся. Поэтому важными стали казаться вопросы исследования недетерминированных конечных автоматов, в том числе — вопросы их экономного представления в памяти компьютера. При разных способах представления автомата в памяти компьютера более важными могут быть либо минимально возможное число вершин, либо минимально возможное число дуг, либо некоторые другие критерии. Именно подобные проблемы и связаны с рассматриваемыми в диссертации алгоритмами.

Целью работы Целью работы является разработка и описание алгоритмов эквивалентного преобразования недетерминированных конечных автоматов, разработка и описание математических моделей, дающих возможность успешного применения подобных алгоритмов в прикладных задачах дискретной оптимизации.

Основные задачи исследования:

1. Разработка и описание нескольких алгоритмов эквивалентного преобразования недетерминированных конечных автоматов.

2. Формулировка и доказательство теорем о корректности этих алгоритмов и свойствах бинарного отношения.

3. Разработка и описание математических моделей поиска в пространствах состояний, дающих возможность успешного применения разработанных алгоритмов в прикладных задачах дискретной оптимизации.

Объект исследования. Объектом исследования являются недетерминированные конечные автоматы Рабина-Скотта (Медведева).

Предмет исследования. Предметом исследования являются алгоритмы работы с недетерминированными конечными автоматами.

Методы исследования. В качестве аппарата исследований применяются методы доказательства теорем дискретной математики и методы разработки алгоритмов.

Результаты исследования. Результатами диссертационного исследования являются новые утверждения, теоремы теории формальных языков, а также новые вычислительные алгоритмы и математические модели.

Научная цовизна. Доказанные утверждения и теоремы, описанные алгоритмы эквивалентного преобразования недетерминированных конечных автоматов, разработанные модели поиска в пространстве состояний на множествах объектов, связанных с недетерминированными конечными автоматами, являются оригинальными разработками автора диссертации совместно с научным руководителем.

Практическая значимость исследования. Полученные результаты могут быть применены в различных задачах минимизации недетерминированных конечных автоматов — в вершинной, дуговой и «звёздно-высотной» минимизации, а также минимизации по некоторым комбинированным критериям. При этом результаты могут быть применены и для создания эвристических алгоритмов решения перечисленных задач дискретной оптимизации.

Достоверность результатов. Достоверность результатов подтверждается приведёнными в диссертации доказательствами утверждений и теорем.

Основные положения, выносимые на защиту.

1. Разработка новых алгоритмов эквивалентного преобразования недетерминированных конечных автоматов.

2. Доказательство теоремы о том, что, применяя операции объединения и дублирования, можно получить любой конечный автомат из заданного конечного автомата с одной компонентой связности через базисный конечный автомат.1.

3. Доказательство теоремы о том, что для двух конечных автоматов возможна любая таблица бинарного отношения в которой нет одина.

ХС точностью до наличия лишних дуг. ковых, пустых строк и столбцов, а также если в «меньшем» нз двух канонических автоматов имеется N состояний, то в «большем» из них — их не более, чем 2N — 1.2.

4. Доказательство теоремы о том, что если в таблице бинарного отношения # строк и столбцов не более, чем N (каждых), то число блоков3 не более, чем N2.

5. Разработка математической модели, которая представляет собой гра-фоподобную структуру на множестве всех эквивалентных автоматов. Доказательство, что эта модель содержит все конечные автоматы с одной компонентой связности, определяющие заданный регулярный язык.

6. Разработка математической модели, которая представляет собой структуру на множестве специально определяемых состояний. Каждое из них содержит подмножество множества блоков, включающее все элементы множества бинарного отношения, а также всё множество циклов (соответствующих циклам базисного автомата), которое описывается специальным образом, например, с помощью регулярных выражений.

7. Демонстрация с помощью примеров, что новые модели и предложенные доказательства помогают разработать более эффективные алгоритмы минимизации (в первую очередь эвристические) и вспомогательные алгоритмы к ним.

Апробация работы. Основные научные и практические результаты исследований по теме диссертации докладывались на:

• XVIII Международной научно-технической конференции «Математические методы и информационные технологии в экономике, социологии и образовании» (г. Пенза, 2006);

• XXI Международной научно-технической конференции «Математические методы и информационные технологии в экономике, социологии и образовании» (г. Пенза, 2008);

Определения «большего» и «меньшего» автоматов приведены в 4 главе.

3Определение блока приведено в 1 главе.

• семинаре кафедры математического анализа физико-математического факультета ГОУ УлГПУ им. И. Н. Ульянова (г. Ульяновск, 2009).

• Всероссийской конференции «Проведение научных исследований в области обработки, хранения, передачи и защиты информации» (г. Ульяновск, 2009). ' ~.

Личный вклад. Изложенные теоремы доказаны лично автором, либо совместно с научным руководителем. При этом части доказательств, связанные с базисным автоматом, а также с операциями дублирования и объединения состояний конечного автомата, принадлежат автору диссертации. Построение двух моделей эквивалентных преобразований конечных автоматов выполнено автором диссертации самостоятельно.

Публикации. Основные результаты диссертации опубликованы в 5 работах, 2 из которых входят в список изданий, рекомендованных ВАК. I.

Структура и объем диссертации

Общий объем диссертации — 115 страниц. Диссертация состоит из введения, четырех глав, заключения, списка используемой литературы из 83 наименований и одного приложения.

1. Алёхина, М. Об одном подходе к моделированию вычислительных устройств / М. Алёхина, А. Лысенко, Б. Мельников // Известия ВУЗов, серия «Физико-математические науки» (Поволжский регион). — № 2 (2008). — С. 2−7.

2. Ахо, А. Теория синтаксического анализа, перевода и компиляции. Т. 1 / А. Ахо, Дж. Ульман. М.: Мир, 1978. — 308 с.

3. Ахо, А. Построение и анализ вычислительных алгоритмов / А. Ахо, Дж. Хопкрофт, Дж. Ульман. М.: Мир, 1979. — 535 с.

4. Ахо, А. Компиляторы: принципы, технологии, инструменты / А. Ахо, Р. Сети, Дж. Ульман. М.-СПб-Киев: Вильяме, 2003. — 768 с.

5. Брауэр, В.

Введение

в теорию конечных автоматов / В. Брауэр. -М.: Радио и связь, 1987. 392 с.

6. Вирт, Н. Алгоритмы + структуры данных = программы / Н. Вирт. -М.: Мир, 1985. 410 с.

7. Вирт, Н. Язык программирования ПАСКАЛЬ// Алгоритмы и организация решения экономических задач / Н. Вирт. -М.: Статистика, 1974. 410 с.

8. Гилл, А. Линейные последовательностные машины. Анализ, синтез и применение / А. Гилл. М.: Наука, 1974. — 287 с.

9. Оллонгрен, А. Определение языков программирования интерпретирующими автоматами / А. Оллонгрен. М.: Мир, 1977. — 287 с.

10. Грунский, И. Анализ поведения конечных автоматов / И.Грунский. -Луганск: Изд-во ЛНПУ, 2003. 318 с.

11. Грунский, И. Синтез и идентификация автоматов / И. Грунский, В Козловский. Киев: Наукова думка, 2004. — 246 с.

12. Гудмаи, С.

Введение

в разработку и анализ алгоритмов / С. Гудман, С. Хидетниеми. М.: Мир, 1981. — 368 с.

13. Дубасова, О. Об одном расширении класса контекстно-свободных языков / О. Дубасова, В. Мельников // Программирование (РАН). 1995. — 6. — С. 46−58.

14. Левитин, А. В. Алгоритмы: введение в разработку и анализ, 4-е издание. / А. В. Левитин. М.: Вильяме, 2006. — 212−215 с.

15. Лекции лауреатов премии Тьюринга за первые двадцать лет: сб. ст. / М.: Мир, 1993. 560 с.

16. Люгер, Д. Ф. Искусственный интеллект: стратегии и методы решения сложных проблем, 4-е издание. / Д. Ф. Люгер. М.: Вильяме, 2003. -212−215 с.

17. Медведев, Ю. О классе событий, допускающих представление в конечном автомате / Ю. Медведев // Автоматы. М.: Иностранная Литература, 1956. — С. 385−401.

18. Мельников, Б. Некоторые следствия условия эквивалентности однозначных скобочных грамматик / Б. Мельников // Вестник Моск. ун-та, сер. Вычисл. матем. и киб-ка. 1991. — № 3. — С. 51−53.

19. Мельников, Б. Об одной классификации последовательностных контекстно-свободных языков и грамматик / Б. Мельников // Вестник Моск. ун-та, сер. Вычисл. матем. и киб-ка. 1993. — № 3. — С. 64−69.

20. Мельников, Б. Подклассы класса контекстно-свободных языков / Б. Мельников. М.: Изд-во МГУ, 1995. — 159 с.

21. Мельников, Б. Ещё раз о конечных автоматах / Б. Мельников // Учёные записки Ульяновского государственного университета. Фундаментальные проблемы математики и механики. Вып. 1, ч. 2. 1996. — С. 1323.

22. Мельников, Б. Ещё раз об объединении состояний недетерминированного конечного автомата / Б. Мельников // Тезисы докладов XI международной научной конференции по проблемам теоретической кибернетики. М.: Изд-во РГГУ. — 1996. — С. 139−141.

23. Мельников, Б. Сведение задач минимизации конечных автоматов к работе с орграфами / Б. Мельников, А. Бросалина // «Математическое моделирование физических, экономических, социальных систем и процессов». Изд-во Ульяновского ун-та, 1998. — С. 15.

24. Мельников, Б. Важный пример к задачам минимизации недетерминированных конечных автоматов / Б. Мельников // Тезисы докладов XII международной научной конференции по проблемам теоретической кибернетики. М.: Изд-во МГУ. — 1999. — С. 153−153.

25. Мельников, Б. Эвристические алгоритмы в специальных задачах дискретной оптимизации / Б. Мельников, А. Радионов // «Дискретный анализ и исследование операций». Новосибирск, Изд-во Института математики, 2000. — С. 190.

26. Мельников, Б. Эвристики в программировании недетерминированных игр / Б. Мельников // Программирование (РАН). 2001. — № 5. — С. 6380.

27. Мельников, Б. Ещё раз об эвристиках для задачи коммивояжёра / Б. Мельников, Н. Романов // Теоретические проблемы информатики и её приложений, вып. 4. Изд-во Саратовского университета, 2001. -С. 81−92.

28. Мельников, Б. Однозначные конечные автоматы / Б. Мельников // Известия ВУЗов, серия «Технические наукрт» (Поволжский регион). -2002. № 2. — С. 9−14.

29. Мельников, Б. Об ш-языках специальных биллиардов / Б. Мельников // Дискретная математика (РАН). 2002. — № 3. — Т. 14. — С. 95−108.

30. Мельников, Б. Программирование недетерминированных игр / Б. Мельников // Российская наука: дорога жизни. Изд-во Октопус.- 2003. С.23−32.

31. Мельников, Б. Мультиэвристический подход к задачам дискретной оптимизации / Б. Мельников // Кибернетика и системный анализ (НАН Украины). 2006. — № 3. — С. 32−42.

32. Мельников, Б. Недетерминированные конечные автоматы / Б. Мельников // ТГУ Тольятти. — 2009. — № 3. — С. 32−42.

33. Мельников, Б. О некоторых алгоритмах эквивалентного преобразования недетерминированных конечных автоматов / Б. Мельников, М. Сайфуллина // Теоретические проблемы информатики и её приложений, вып. 4. Известия ВУЗов, Математика. — 2009. — № 4. — С. 67−71.

34. Новиков, Ф. Дискретная математика для программистов / Ф.Новиков.- СПб: Питер, 2002. 304 с.

35. Разборов, A. Theoretical Computer Science: взгляд математика / А. Разборов // Компьютерра. 2001. — № 2. — С. 39−46.

36. Рассел, С. Искусственный интеллект: современный подход, 2-е издание. / С. Рассел, П. Норвиг. М.: Вильяме, 2006. — 122−125 с.

37. Саломаа, А. Жемчужины теории формальных языков / А. Саломаа.- М.: Мир, 1986. 159 с.

38. Трахтенброт, Б. Конечные автоматы: поведение и синтез / Б. Трахтенброт, Я. Бардзинь. М.: Наука, 1970. — 400 с.

39. Уфнаровекпй, В. Комбинаторные и асимптотические методы в алгебре / В. Уфнаровский // Итоги науки и техн. Сер. «Соврем, пробл. мат.».- М.: ВИНИТИ. 1990. — № 57. — С. 5−177.

40. Харари, Ф. Теория графов / Ф.Харари. М.: Мир, 1973. — 300 с.

41. Хопкрофт, Дж. Алгоритм для минимизации конечного автомата, Кибернетический сборник, новая серия, вып. 11 / Дж.Хопкрофг. -М.: Мир, 1974. 177−184 с.

42. Чирков, М. Основы общей теории конечных автоматов / М. Чирков.- Л.: Изд-во ЛГУ, 1975. 280 с.

43. Шень, А. Программирование: теоремы и задачи / А. Шень. М.: Изд-во МЦНМО, 2004. — 285 с.

44. Яблонский, С. Дискретная математика / С. Яблонский. — М.: Наука, 1979. 272 с.

45. Языки и автоматы / М. :Мир, 1975. 358 с.

46. Bellmore, М. The Traveling Salesman Problem: A Survey / M. Bellmore, G. Nemhauser // Operation Reasearch. Vo.16 (1968). — P. 538−558.

47. Belov, A. Monomial algebras / A. Belov, V. Borisenko, V. Latyshev // Journal of Mathematical Sciences (New York). 87 (1997), No. 3. — P. 34 633 575.

48. Bergman, G. The Diamond Lemma for Ring Theory / G. Bergman // Advances in Mathematics. 29 (1978). — P. 178−218.

49. Brzozowski, J.A. Open problems about regular languages, In: Ronald V. Book, editor, Formal language theory—Perspectives and open problems / J.A. Brzozowski. N. Y.: Academic Press, 1980. — 23—47 c.

50. Chomsky, N. Finite state languages, Inform, and Control / N. Chomsky, G.A. Miller. M.: Мир, 1962. — 233−255 с.

51. Eilenberg, S. Automata, Languages and Machines. Vol. A / S.Eilenberg. N. Y.: Academic Press. 1974. — 312 c.

52. Dejean, F. On a question of Eggan / F. Dejean, M. Schutzenberger. — Information and Control 9(1), 1966. 23−25 c.

53. Hashiguchi, K. Algorithms for determining relative star height and star height / K. Hashiguchi // Inform. Comput. 78 (1987). — P. 124−169.

54. Hromkovic, J. Algorithmics for Hard Problems. Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics / J. Hromkovic. Springer, 2004. — 548 c.

55. Jiang, T. Minimal NFA Problems are Hard / T. Jiang, B. Ravikumar // SIAM J. Comput. 22 (1993). — P. 1117−1141.

56. Kameda, T. On the state minimization of nondeterministic finite automata / T. Kameda, P. Weiner // IEEE Trans, on Computers. C-19 (1970). -P. 617−627.

57. Eggen, L. C Transition graphs and the star-height of regular events / L. CEggen // The Michigan Mathematical Journal. 1963. — P. 385−397.

58. Mealy, G. H A Method to Synthesizing Sequential Circuits / G. H Mealy // Bell Systems Technical Journal. 1955. — P. 1045−1079.

59. Melnikov, В. Some more on the finite automata / B. Melnikov, A. Vakhitova // The Korean Journal of Computational and Applied Mathematics. 5 (1998) No. 3. — P. 495−506.

60. Melnikov, B. A new algorithm of the state-minimization for the nondeterministic finite automata / B. Melnikov // The Korean Journal of Computational and Applied Mathematics. 6 (1999) No. 2. — P. 277−290.

61. Melnikov, B. Once more about the state-minimization of the nondeterministic finite automata / B. Melnikov // The Korean Journal of Computational and Applied Mathematics. 7 (2000) No. 3. — P. 655−662.

62. Melnikov, B. Edge-minimization of non-deterministic finite automata /B. Melnikov, A. Melnikova // The Korean Journal of Computational and Applied Mathematics. 8 (2001) No.3. — P. 469−479.

63. Melnikov, B. Some properties of the basis finite automaton / B. Melnikov, A. Melnikova // The Korean Journal of Computational and Applied Mathematics. 9 (2002) No. 1. — P. 131−150.

64. Melnikov, B. Possible edges of a finite automaton defining the given regular language / B. Melnikov, N. Sciarini-Guryanova // The Korean Journal of Computational and Applied Mathematics. 9 (2002) No. 2. — P. 475−485.

65. Melnikov, B. Discrete optimization problems some new heuristic approaches / B. Melnikov // IEEE Сотр. Soc. Press Ed. -2005. — P. 73−80.

66. Melnikov, B. Some special heuristics for discrete optimization problems / B. Melnikov, A. Radionov, V. Gumayunov // The 8th International Conference on Enterprise of Information Systems. 2006. — P. 91−95.

67. Moore, E.F. Gedanken-experiments on Sequential Machines. Automata Studies, Annals of Mathematical Studies / E.F.Moore. Princeton, N.J.: Princeton University Press, 1956. — 129—153 c.

68. Polak, L. Minimalizations of NFA using universal automata / L. Polak // Int. J. of Found, of Computer Science. 16 (2005) No. 5. — P. 999−1010.

69. Pcrrin, D. Finite Automata. Handbook of Theoret. Comput. Sci., Vol. A / D. Perrin. Elsevier Sci. Publ., 1990. — 1−57 c.

70. Rabin, M. Finite automata and their decision problems / M. Rabin, D. Scott // IBM J. Research and Development. 3 (1959). — P. 114−125. (Имеется русский перевод в кн.: «Кибернетический сборник, вып. 4». — М.: Иностранная Литература. — 1962. — С. 58−91.).

71. Staiger, L. cj-Languages. Handbook of Formal Languages, Vol.3 / L. Staiger // Berlin: Springer. 1997. — P. 339−387.

72. Stanevichene, L.I. An algorithm for transformation of finite automata to regular expressions / L.I. Stanevichene, A.A. Vylitok // Informatica. 11 (2000) No. 1. — P. 49−54.

73. Thomas, W. Automata on Infinite Objects / W. Thomas // Handbook of Theoret, Comput. Sci., Vol. B, Elsevier Sci. Publ. 1990. — P. 133−191.

74. Vakhitova, A. The basis automaton for the given regular language / A. Vakhitova // The Korean Journal of Computational and Applied Mathematics. 6 (1999) No. 3. — P. 617−624.

75. Wood, D. Grammar and L Forms: an Introduction / D.Wood. -Berlin: Springer, 1980. 328 c.