Дескриптивная сложность некоторых преобразований регулярных языков

0.1 Регулярные языки и конечные автоматы.

Теория регулярных языков и конечных автоматов является весьма значительной частью общей теории формальных языков. Начало изучения конечных автоматов можно заметить в 40-х гг. в работе Мак-Каллоха и Питса [34], где для моделирования нейронной сети использовалось устройство с конечным набором состояний. С этого момента регулярные языки и конечные автоматы изучаются чрезвычайно интенсивно. Одним из ранних результатов явилась теорема К лини [29], устанавливающая эквивалентность класса языков, задаваемых регулярными выражениями и конечными автоматами, а также появление автомата с выходом в работах Мили [35] и Мура [37], недетерминированных конечных автоматов в работах Рабина и Скота [45] и характеризация регулярных языков при помощи конгруэнции конечного индекса в работах Майхилла [40] и Нерода [43]. В соответствии с иерархией формальных языков, которую в 50-х гг. предложил Хомский [16], регулярные языки относятся к третьему типу (после контекстно-зависимых и контекстно-свободных языков) и являются самым простым классом в этой иерархии.

Регулярные языки, оставаясь довольно простым объектом, способны описывать самые разные системы. Именно поэтому регулярные языки и конечные автоматы с каждым годом находят все больше и больше применений: это и приложения в задачах обработки текста и лексических анализаторах, и использование в вычислениях при помощи ДНК, и применение в задачах параллельной обработки данных, и многое другое.

Классическим способом задания регулярного языка является детерминированный конечный автомат. Такой автомат имеет конечный набор состояний и конечный набор правил, по которым изменяется текущее состояние в зависимости от входного символа. Одно из состояний является начальным, часть состояний объявлены заключительными. Автомат, начиная читать последовательность символов из начального состояния, меняет свое текущее состояние в соответствии со своим набором правил и заканчивает чтение последовательности в некотором состоянии. Если это состояние является заключительным, то последовательность символов принимается, в противном случае — отвергается. Детерминированный конечный автомат в виде подобного управляющего устройства изображен на рисунке 1.

Рис. 1: Пример представления детерминированного автомата в виде управляющего устройства.

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

Другой не менее распространенный способ задания регулярного языка — это регулярное выражение. Выделяют простые регулярные выражения (пустое множество, пустая строка и отдельные буквы) и составные (выражения, полученные с использованием операций — сложения, произведения и итерации). Сумме двух регулярных выражений соответствует объединение слов, удовлетворяющих одному из этих выражений. Произведению двух регулярных выражений соответствует множество слов, каждое из которых составлено из последовательной записи некоторого слова первого и некоторого слова из второго. Итерации регулярного выражения соответствует объединение всех возможных степеней данного выражения, начиная с нулевой (т.е. с пустого слова). С регулярным языком крайне естественно связать минимальную длину регулярного выражения, задающего данный язык, — длина самой компактной текстовой записи регулярного языка в фиксированной нотации. С длиной регулярного выражения прямо связано количество состояний в недетерминированном конечном автомате — автомате, который может проводить вычисления, используя параллельно сразу несколько правил в разных потоках. Таким образом, вполне естественно оценивать сложность языка при помощи минимального размера недетерминированного конечного автомата, который этот язык распознает.

1. Гасфилд Д., Строки, деревья и последовательности в алгоритмах. Информатика и вычислительная биология — БХВ-Петербург, 2003. — 656 с.

2. Кудрявцев В. В., Алешин С. В., Подколзин А. С., Введение в теорию автоматов — М.: Наука, 1985. — 320 с.

3. Левенштейн В. И., Двоичные коды с исправлением выпадений, вставок и замещений символов // Доклады Академии наук СССР — 1965. Т. 163 (4) — С. 846−848.

4. Лупанов О. В., О сравнении двух типов конечных источников 11 Проблемы кибернетики — 1963. — Вып. 9. — С. 321−326.

5. Маслов А. Н., Оценки числа состояний конечных автоматов // Доклады Академии наук СССР 1970. — Т. 194 (6). — С. 12 661 268.

6. Маслов А. Н., О циклических перестановках языков // Проблемы передачи информации — 1973. — Т. 9 (4). — С. 81−87.

7. Чашкин А. В., Лекции по дискретной математике — М.: МГУ, 2007. — 261 с.

8. Ananichev D. S., Volkov М. V., Dighaphs admiting only coloring with long synchronizing instructions, в печати.

9. Baeza-Yates R., Ribeiro B. (eds.), Modern Information Retrieval — Addison-Wesley, 1999. — 544 p.

10. Birget J.-C., Intersection and union of regular languages and state complexity // Information Processing Letters — 1992. — V. 43. — P. 185−190.

11. Birget J.-C., Partial orders on words, minimal elements of regular languages, and state complexity // Theoretical Computer Science — 1993. — V. 119 (2). P. 267−291.

12. Calude C., Salomaa K., Yu S., Metric lexical analysis // Lecture Notes in Computer Science — 2001. — V. 2214. — P. 48−59.

13. Campeanu C., Culik K., Salomaa K., Yu S., State complexity of basic operations on finite languages // Lecture Notes in Computer Science- 2001. V. 2214. — P. 60−70.

14. Campeanu C., Salomaa K., Yu S., Tight lower bound for the state complexity of shuffle of regular language J/ Journal of Automata, Lanugages and Combinatorics — 2002. — V. 7. — P. 303−310.

15. Cerny J., Poznamka к homogennym eksperimentom s konecnymi automatami // Mat.-Fyz. Cas. Slovensk. Akad. Vied. — 1964. — V. 14. — P. 208−216.

16. Chomsky N., Three models for the description of language // IRE Transactions on Information Theory — 1956. — V. 2. — P. 113−124.

17. Domaratzki M., State complexity and proportional removals // Journal of Automata, Lanugages and Combinatorics — 2002. — V. 7. P. 455−468.

18. El-Mabrouk N., On the size of minimal automata for approximate string matching // Institut Gaspard Monge, Universite de Marne-la-Vallee 1997. — V. IGM97−19 (technical report).

19. Epifanio C., Gabriele A., Mignosi F., Restivo A., Sciortino M., Languages with mismatches // Theoretical Computer Science — 2007. V. 385 (1−3). — P. 152−166.

20. Gruber H., Holzer M., Finding lower bounds for nondeterministic state complexity is hard // Lecture Notes in Computer Science — 2006. V. 4036. — P. 363−374.

21. Gruber H., Holzer M., Inapproximability of nondeterministic state and transition complexity assuming P Ф NP // Lecture Notes in Computer Science — 2007. — V. 4588. — P. 205−216.

22. Han Y.-S., Salomaa K., State complexity of union and intersection of finite languages // Lecture Notes in Computer Science — 2007. — V. 4588. P. 217−228.

23. Hopcroft J. E., An nlogn algorithm for minimizing states in finite automaton // Stanford University — 1971. — CS-71−190 (technical report).

24. Hopcroft J. E., Motwani R., Ullman J. D., Introduction to Automata Theory, Languages, and Computation — Addison-Wesley, 2001 — 521 p.

25. Jirasek J., Jiraskova G., Szabari A., Deterministic Blow-Ups of Minimal Nondeterministic Finite Automata over a Fixed Alphabet // Lecture Notes in Computer Science — 2007. — V. 4588. — P. 254 265.

26. Jiraskova G., Magic Numbers and Ternary Alphabet // Lecture Notes in Computer Science — 2009. — V. 5583. — P. 300−311.

27. Jiraskova G., Okhotin A., On the state complexity of operations on two-way finite automata // Lecture Notes in Computer Science — 2008. V. 5257. — P. 443−454.

28. Karhumaki J., Automata and Formal Languages // http://www.math.utu.fi/en/home/karhumak/Automata2007.pdf (электронные материалы лекций) — 2007.

29. Kleene S. С., Representation of events in nerve nets and finite automata // Automata Studies — 1956. — P. 2−42.

30. Kukich K., Techniques for automatically correcting words in text // ACM Computing Surveys 1992. — V. 24 (4). — P. 377−439.

31. Kutrib M., Holzer M., Unary language operations and their nondeterministic state complexity /j Lecture Notes in Computer Science 2003. — V. 2450. — P. 162−172.

32. Kutrib M., Holzer M., State complexity of basic operations on nondeterministic finite automata // Lecture Notes in Computer Science 2003. — V. 2608. — P. 151−160.

33. Kutrib M., Holzer M., Nondeterministic descriptional complexity of regular languages // International Journal of Foundations of Computer Science 2003. — V. 6 (14). — P. 1087−1102.

34. McCulloch W. S., Pitts W., A logical calculus of the ideas immanent in nervous activity // Bulletin of Mathematical Biophysics — 1943. — V. 5. P. 115−133.

35. Mealy G. H., A method for synthesizing sequential circuits j I Bell System Technical Journal — 1955. — V. 34(5). — P. 1045−1079.

36. Meyer A. R., Fischer M. J., Economy of description by automata, grammars, and formal systems // Proceedings of the Annual Symposium on Foundations of Computer Science — 1971. — P. 188 191.

37. Moore E. F., Gedanken experiments on sequential machines // Automata Studies — 1956. — P. 129−153.

38. Moore F., On the bounds for set-state size in the proofs of equivalence between deterministic, nondeterministic and two-way finite automata 11 IEEE Transactions on Computers — 1971. — V. 20. — P. 12 111 214.

39. Myers G., Algorithmic advances for searching biosequence databases // Suhai S. (ed.) Computational Methods in Genome Research — Plenum Press, 1994. — P. 121−135.

40. Myhill J., Finite automata and the representation of events // Wright Patterson AFB, Ohio — 1957. — WADD TR-57−625. — P. 112−137 (technical report).

41. Navarro G., A guided tour to approximate string matching // ACM Computing Surveys — 2001. — V. 33. — P. 31−88.

42. Navarro G., NR-grep: a fast and flexible pattern-matching tool // Software — Practice and Experience — 2001. — V. 31. — P. 12 651 312.

43. Nerode A., Linear automata transformation // Proceedings of AMS1958. — V. 9. — P. 541−544.

44. Okhotin A., State complexity of linear conjunctive grammars // Journal of Automata, Languages and Combinatorics — 2004. V. 9(2/3). P. 365−381.

45. Rabin M., Scott D., Finite automata and their decision problems // IBM Journal of Research and Development — 1959. — V. 3 (2). — P. 114−125.

46. Sakarovitch J., Elements de theorie des automates — Vuibert, 2003. 816 p.

47. Salomaa A., On the reducibility of events represented in automata j/ Annales Academiae Scientiarium Fennicae, Series A, I. Mathematica- 1964. V. 353.

48. Salomaa A., Wood D., Yu S., On the state complexity of reversals of regular languages // Theoretical Computer Science —2007. — V. 383 (2−3). — P. 140−152.

49. Salomaa A., Salomaa K., Yu S., State complexity of combined operations // Theoretical Computer Science — 2004. — V. 320 (2−3).P. 315−329.51.