Обычный язык

Формальный язык, который можно выразить с помощью регулярного выражения.

В теоретической информатике и теории формального языка регулярный язык (также называемый рациональным языком ) ^{[1] [2]} — это формальный язык , который может быть определен регулярным выражением в строгом смысле в теоретической информатике (в отличие от многих современных систем регулярных выражений, которые дополнены функциями , позволяющими распознавать нерегулярные языки).

В качестве альтернативы регулярный язык можно определить как язык, распознаваемый конечным автоматом . Эквивалентность регулярных выражений и конечных автоматов известна как теорема Клини ^[3] (в честь американского математика Стивена Коула Клини ). В иерархии Хомского регулярные языки — это языки, генерируемые грамматиками типа 3 .

Формальное определение

Совокупность регулярных языков над алфавитом Σ определяется рекурсивно следующим образом:

• Пустой язык Ø — это обычный язык.
• Для каждого a ∈ Σ ( a принадлежит Σ) одноэлементный язык { a  } является регулярным языком.
• Если A — регулярный язык, то A * ( звезда Клини ) — регулярный язык. В связи с этим пустой строковый язык {ε} также является регулярным.
• Если A и B — регулярные языки, то A ∪ B (объединение) и A • B (конкатенация) — регулярные языки.
• Никакие другие языки над Σ не являются регулярными.

Синтаксис и семантику регулярных выражений см. в разделе Регулярные выражения.

Примеры

Все конечные языки регулярны; в частности, язык пустых строк {ε} = Ø* является регулярным. Другие типичные примеры включают язык, состоящий из всех строк в алфавите { a , b }, которые содержат четное число a , или язык, состоящий из всех строк вида: несколько a , за которыми следует несколько b .

Простым примером языка, который не является регулярным, является набор строк { a ⁿ b ⁿ | n ≥ 0}. ^[4] Интуитивно, его нельзя распознать с помощью конечного автомата, поскольку конечный автомат имеет конечную память и не может запомнить точное количество букв a. Методы строгого доказательства этого факта приведены ниже.

Эквивалентные формализмы

Регулярный язык удовлетворяет следующим эквивалентным свойствам:

1. это язык регулярных выражений (согласно определению выше)
2. это язык, принимаемый недетерминированным конечным автоматом (НКА) ^{[примечание 1] [примечание 2]}
3. это язык, принимаемый детерминированным конечным автоматом (ДКА) ^{[примечание 3] [примечание 4]}
4. его можно получить с помощью обычной грамматики ^{[примечание 5] [примечание 6]}
5. это язык, принимаемый переменным конечным автоматом
6. это язык, принимаемый двусторонним конечным автоматом
7. его можно сгенерировать с помощью префиксной грамматики
8. его может принять машина Тьюринга , доступная только для чтения
9. его можно определить в монадической логике второго порядка ( теорема Бюхи–Элгота–Трактенброта ) ^[5]
10. он распознаётся некоторым конечным синтаксическим моноидом M , то есть является прообразом { w ∈ Σ ^* | f ( w ) ∈ S } подмножества S конечного моноида M при гомоморфизме моноида f : Σ ^* → M из свободного моноида в его алфавите ^{[примечание 7]}
11. число классов эквивалентности его синтаксической конгруэнтности конечно. ^{[примечание 8] [примечание 9]} (Это число равно числу состояний минимального детерминированного конечного автомата, принимающего L .)

Свойства 10. и 11. являются чисто алгебраическими подходами к определению регулярных языков; аналогичный набор утверждений может быть сформулирован для моноида M ⊆ Σ ^* . В этом случае эквивалентность над M приводит к понятию распознаваемого языка.

Некоторые авторы используют одно из вышеперечисленных свойств, отличное от «1», в качестве альтернативного определения регулярных языков.

Некоторые из приведенных выше эквивалентностей, особенно те, что входят в первые четыре формализма, в учебниках называются теоремой Клини . Какой именно из них (или какое подмножество) называется таковым, варьируется между авторами. Один учебник называет эквивалентность регулярных выражений и НКА («1.» и «2.» выше) «теоремой Клини». ^[6] Другой учебник называет эквивалентность регулярных выражений и ДКА («1.» и «3.» выше) «теоремой Клини». ^[7] Два других учебника сначала доказывают выразительную эквивалентность НКА и ДКА («2.» и «3.»), а затем формулируют «теорему Клини» как эквивалентность регулярных выражений и конечных автоматов (последние, как говорят, описывают «распознаваемые языки»). ^{[2] [8]} Лингвистически ориентированный текст сначала приравнивает регулярные грамматики («4. выше) к DFA и NFA, называет языки, генерируемые (любым из) из них «регулярными», после чего вводит регулярные выражения, которые он называет «рациональными языками», и, наконец, формулирует «теорему Клини» как совпадение регулярных и рациональных языков. ^[9] Другие авторы просто определяют «рациональное выражение» и «регулярные выражения» как синонимы и делают то же самое с «рациональными языками» и «регулярными языками». ^{[1] [2]}

По-видимому, термин «регулярный» берет свое начало в техническом отчете 1951 года, в котором Клини ввел «регулярные события» и открыто приветствовал «любые предложения относительно более описательного термина» . ^[10] Ноам Хомский в своей основополагающей статье 1959 года сначала использовал термин «регулярный» в другом значении (имея в виду то, что сегодня называется « нормальной формой Хомского » ), ^[11] но заметил, что его «конечно-государственные языки» эквивалентны «регулярным событиям» Клини . ^[12]

Свойства закрытия

Регулярные языки замкнуты относительно различных операций, то есть, если языки K и L являются регулярными, то таковым является и результат следующих операций:

• теоретико -множественные булевы операции : объединение K ∪ L , пересечение K ∩ L и дополнение L , следовательно, и относительное дополнение K − L. ^[13 ]
• обычные операции: K ∪ L , конкатенация ⁠ ⁠ ${\displaystyle K\circ L}$ и звезда Клини L ^* . ^[14]
• три операции: гомоморфизм строк , обратный гомоморфизм строк и пересечение с регулярными языками. Как следствие , они замкнуты относительно произвольных конечных преобразований , как фактор K / L с регулярным языком. Более того, регулярные языки замкнуты относительно факторных с произвольными языками: если L является регулярным , то L / K является регулярным для любого K. ^[15]
• обратный (или зеркальный) L ^R . ^[16] Если задан недетерминированный конечный автомат для распознавания L , то автомат для L ^R может быть получен путем обращения всех переходов и замены начальных и конечных состояний. Это может привести к нескольким начальным состояниям; для их соединения можно использовать ε-переходы.

Свойства разрешимости

При наличии двух детерминированных конечных автоматов A и B можно решить, принимают ли они один и тот же язык. ^[17] Как следствие, используя указанные выше свойства замыкания, следующие проблемы также разрешимы для произвольно заданных детерминированных конечных автоматов A и B с принятыми языками L _A и L _B соответственно:

• Сдерживание: L _A ⊆ L _B  ? ^{[примечание 10]}
• Дизъюнктность: L _A ∩ L _B = {} ?
• Пустота: L _A = {} ?
• Универсальность: L _A = Σ ^*  ?
• Принадлежность: если a ∈ Σ ^* , то a ∈ L _B  ?

Для регулярных выражений проблема универсальности является NP-полной уже для одноэлементного алфавита. ^[18] Для более крупных алфавитов эта проблема является PSPACE-полной . ^[19] Если регулярные выражения расширить, чтобы разрешить также оператор возведения в квадрат , с " A ² ", обозначающим то же самое, что и " AA ", все еще можно будет описать только регулярные языки, но проблема универсальности имеет нижнюю границу экспоненциального пространства, ^{[20] [21] [22]} и фактически является полной для экспоненциального пространства относительно редукции за полиномиальное время. ^[23]

Для фиксированного конечного алфавита теория множества всех языков — вместе со строками, принадлежностью строки языку и для каждого символа функцией добавления символа к строке (и без других операций) — разрешима, и ее минимальная элементарная подструктура состоит именно из регулярных языков. Для двоичного алфавита теория называется S2S . ^[24]

Результаты сложности

В теории вычислительной сложности класс сложности всех регулярных языков иногда называют REGULAR или REG , и он равен DSPACE (O(1)), задачам принятия решений , которые могут быть решены в постоянном пространстве (используемое пространство не зависит от размера входных данных). REGULAR ≠ AC 0 , поскольку он (тривиально) содержит проблему четности определения того, является ли число единичных битов во входных данных четным или нечетным, и эта проблема отсутствует в AC ⁰ . ^[25] С другой стороны, REGULAR не содержит AC ⁰ , поскольку нерегулярный язык палиндромов или нерегулярный язык оба могут быть распознаны в AC ⁰ . ^[26] ${\displaystyle \{0^{n}1^{n}:n\in \mathbb {N} \}}$

Если язык не является регулярным, для его распознавания требуется машина с по крайней мере Ω (log log  n ) пространства (где n — размер входных данных). ^[27] Другими словами, DSPACE( o (log log  n )) соответствует классу регулярных языков. На практике большинство нерегулярных задач решаются машинами, занимающими по крайней мере логарифмическое пространство .

Расположение в иерархии Хомского

Регулярный язык в классах иерархии Хомского

Чтобы найти регулярные языки в иерархии Хомского , можно заметить, что каждый регулярный язык является контекстно-свободным . Обратное неверно: например, язык, состоящий из всех строк, имеющих одинаковое количество символов a и b , является контекстно-свободным, но не регулярным. Чтобы доказать, что язык не является регулярным, часто используют теорему Майхилла–Нерода и лемму о накачке . Другие подходы включают использование свойств замыкания регулярных языков ^[28] или количественную оценку сложности Колмогорова . ^[29]

Важные подклассы регулярных языков включают в себя

• Конечные языки, содержащие только конечное число слов. ^[30] Это регулярные языки, поскольку можно создать регулярное выражение , которое является объединением всех слов в языке.
• Языки без звезд , те, которые можно описать регулярным выражением, составленным из пустого символа, букв, конкатенации и всех булевых операторов (см. алгебру множеств ), включая дополнение , но не звезду Клини : этот класс включает все конечные языки. ^[31]

Количество слов в обычном языке

Пусть обозначает число слов длины в . Обычная производящая функция для L — это формальный степенной ряд ${\displaystyle s_{L}(n)}$ ${\displaystyle n}$ ${\displaystyle L}$

${\displaystyle S_{L}(z)=\sum _{n\geq 0}s_{L}(n)z^{n}\ .}$

Производящая функция языка L является рациональной функцией , если L является регулярным. ^[32] Следовательно, для каждого регулярного языка последовательность является константно-рекурсивной ; то есть существуют целая константа , комплексные константы и комплексные многочлены такие, что для каждого количество слов длины в равно . ^{[33] [34] [35] [36]} ${\displaystyle L}$ ${\displaystyle s_{L}(n)_{n\geq 0}}$ ${\displaystyle n_{0}}$ ${\displaystyle \lambda _{1},\,\ldots ,\,\lambda _{k}}$ ${\displaystyle p_{1}(x),\,\ldots ,\,p_{k}(x)}$ ${\displaystyle n\geq n_{0}}$ ${\displaystyle s_{L}(n)}$ ${\displaystyle n}$ ${\displaystyle L}$ ${\displaystyle s_{L}(n)=p_{1}(n)\lambda _{1}^{n}+\dotsb +p_{k}(n)\lambda _{k}^{n}}$

Таким образом, нерегулярность некоторых языков может быть доказана путем подсчета слов заданной длины в . Рассмотрим, например, язык Дика строк сбалансированных скобок. Количество слов длины в языке Дика равно каталонскому числу , которое не имеет вида , что свидетельствует о нерегулярности языка Дика. Необходимо соблюдать осторожность, поскольку некоторые собственные значения могут иметь одинаковую величину. Например, количество слов длины в языке всех четных двоичных слов не имеет вида , но количество слов четной или нечетной длины имеют этот вид; соответствующие собственные значения равны . В общем случае для каждого регулярного языка существует константа такая, что для всех количество слов длины асимптотически равно . ^[37] ${\displaystyle L'}$ ${\displaystyle L'}$ ${\displaystyle 2n}$ ${\displaystyle C_{n}\sim {\frac {4^{n}}{n^{3/2}{\sqrt {\pi }}}}}$ ${\displaystyle p(n)\lambda ^{n}}$ ${\displaystyle \lambda _{i}}$ ${\displaystyle n}$ ${\displaystyle p(n)\lambda ^{n}}$ ${\displaystyle 2,-2}$ ${\displaystyle d}$ ${\displaystyle a}$ ${\displaystyle dm+a}$ ${\displaystyle C_{a}m^{p_{a}}\lambda _{a}^{m}}$

Дзета -функция языка L равна ^[32]

${\displaystyle \zeta _{L}(z)=\exp \left({\sum _{n\geq 0}s_{L}(n){\frac {z^{n}}{n}}}\right).}$

Дзета-функция регулярного языка в общем случае не является рациональной, но дзета-функция произвольного циклического языка является таковой. ^{[38] [39]}

Обобщения

Понятие регулярного языка было обобщено на бесконечные слова (см. ω-автоматы ) и на деревья (см. древовидный автомат ).

Рациональный набор обобщает понятие (регулярного/рационального языка) на моноиды, которые не обязательно свободны . Аналогично, понятие распознаваемого языка (конечным автоматом) имеет тезку как распознаваемое множество над моноидом, который не обязательно свободен. Говард Штраубинг замечает в связи с этими фактами, что «Термин «регулярный язык» немного неудачен. Статьи, на которые повлияла монография Эйленберга [ ^40], часто используют либо термин «распознаваемый язык», который относится к поведению автоматов, либо «рациональный язык», который относится к важным аналогиям между регулярными выражениями и рациональными степенными рядами . (На самом деле, Эйленберг определяет рациональные и распознаваемые подмножества произвольных моноидов; эти два понятия, в общем, не совпадают.) Эта терминология, хотя и лучше мотивирована, так и не прижилась, и «регулярный язык» используется почти повсеместно». ^[41]

Рациональный ряд — это еще одно обобщение, на этот раз в контексте формального степенного ряда над полукольцом . Этот подход приводит к взвешенным рациональным выражениям и взвешенным автоматам . В этом алгебраическом контексте регулярные языки (соответствующие рациональным выражениям с булевым весом) обычно называются рациональными языками . ^{[42] [43]} Также в этом контексте теорема Клини находит обобщение, называемое теоремой Клини-Шютценбергера.

Учимся на примерах

Примечания

1. 1. ⇒ 2. по алгоритму построения Томпсона
2. 2. ⇒ 1. по алгоритму Клини или с использованием леммы Ардена
3. 2. ⇒ 3. по конструкции powerset
4. 3. ⇒ 2. поскольку первое определение сильнее второго
5. 2. ⇒ 4. см. Хопкрофт, Ульман (1979), Теорема 9.2, стр.219
6. 4. ⇒ 2. см. Хопкрофт, Ульман (1979), Теорема 9.1, стр.218
7. 3. ⇔ 10. по теореме Майхилла–Нерода
8. u ~ v определяется как: uw ∈ L тогда и только тогда, когда vw ∈ L для всех w ∈Σ ^*
9. 3. ⇔ 11. см. доказательство в статье Syntactic monoid , а также см. стр. 160 в Holcombe, WML (1982). Алгебраическая теория автоматов . Cambridge Studies in Advanced Mathematics. Vol. 1. Cambridge University Press . ISBN 0-521-60492-3. Збл  0489.68046.
10. Проверьте, выполняется ли условие L _A ∩ L _B = L _A . Определение этого свойства в общем случае является NP-трудной задачей ; см. Файл:RegSubsetNP.pdf для иллюстрации идеи доказательства.

Ссылки

• Берстель, Жан ; Ройтенауэр, Кристоф (2011). Некоммутативные рациональные ряды с приложениями . Энциклопедия математики и ее приложений. Том 137. Кембридж: Cambridge University Press . ISBN 978-0-521-19022-0. Збл  1250.68007.
• Эйленберг, Сэмюэл (1974). Автоматы, языки и машины. Том A. Чистая и прикладная математика. Том 58. Нью-Йорк: Academic Press. Zbl  0317.94045.
• Саломаа, Арто (1981). Драгоценности формальной теории языка . Pitman Publishing. ISBN 0-273-08522-0. Збл  0487.68064.
• Сипсер, Майкл (1997). Введение в теорию вычислений . PWS Publishing. ISBN 0-534-94728-X. Збл  1169.68300.Глава 1: Регулярные языки, стр. 31–90. Подраздел «Разрешимые проблемы, касающиеся регулярных языков» раздела 4.1: Разрешимые языки, стр. 152–155.
• Филипп Флажоле и Роберт Седжвик, Аналитическая комбинаторика : Символическая комбинаторика. Электронная книга, 2002.
• Джон Э. Хопкрофт; Джеффри Д. Ульман (1979). Введение в теорию автоматов, языки и вычисления . Эддисон-Уэсли. ISBN 0-201-02988-X.
• Альфред В. Ахо и Джон Э. Хопкрофт и Джеффри Д. Ульман (1974). Проектирование и анализ компьютерных алгоритмов . Эддисон-Уэсли. ISBN 9780201000290.

1. Руслан Митков (2003). Оксфордский справочник по компьютерной лингвистике. Oxford University Press. стр. 754. ISBN 978-0-19-927634-9.
2. Марк В. Лоусон (2003). Конечные автоматы. CRC Press. С. 98–103. ISBN 978-1-58488-255-8.
3. Шэн Ю (1997). «Регулярные языки». В Гжегоже Розенберге; Арто Саломаа (ред.). Справочник по формальным языкам: Том 1. Слово, язык, грамматика . Спрингер. п. 41. ИСБН 978-3-540-60420-4.
4. Эйленберг (1974), стр. 16 (Пример II, 2.8) и стр. 25 (Пример II, 5.2).
5. M. Weyer: Глава 12 - Разрешимость S1S и S2S, стр. 219, Теорема 12.26. В: Erich Grädel, Wolfgang Thomas, Thomas Wilke (ред.): Автоматы, логика и бесконечные игры: руководство по современным исследованиям. Lecture Notes in Computer Science 2500, Springer 2002.
6. Роберт Седжвик; Кевин Дэниел Уэйн (2011). Алгоритмы. Addison-Wesley Professional. стр. 794. ISBN 978-0-321-57351-3.
7. Жан-Поль Аллуш; Джеффри Шаллит (2003). Автоматические последовательности: теория, приложения, обобщения. Cambridge University Press. стр. 129. ISBN 978-0-521-82332-6.
8. Кеннет Розен (2011). Дискретная математика и ее приложения, 7-е издание. McGraw-Hill Science. С. 873–880.
9. Хорст Бунке; ​​Альберто Санфелиу (январь 1990). Синтаксическое и структурное распознавание образов: теория и приложения. World Scientific. стр. 248. ISBN 978-9971-5-0566-0.
10. Стивен Коул Клини (декабрь 1951 г.). Представление событий в нервных сетях и конечных автоматах (PDF) (исследовательский меморандум). ВВС США / Корпорация RAND.Здесь: стр.46
11. Ноам Хомский (1959). «О некоторых формальных свойствах грамматик» (PDF) . Информация и управление . 2 (2): 137–167. doi : 10.1016/S0019-9958(59)90362-6 .Здесь: Определение 8, стр.149
12. Хомский 1959, сноска 10, стр. 150
13. Саломаа (1981) стр.28
14. Саломаа (1981) стр.27
15. Fellows, Michael R. ; Langston, Michael A. (1991). "Проблемы конструктивности в графовых алгоритмах". В Myers, J. Paul Jr.; O'Donnell, Michael J. (ред.). Конструктивность в компьютерных науках, Летний симпозиум, Сан-Антонио, Техас, США, 19-22 июня, Труды . Заметки лекций по компьютерным наукам. Том 613. Springer. стр. 150–158. doi :10.1007/BFB0021088. ISBN 978-3-540-55631-2.
16. Хопкрофт, Ульман (1979), Глава 3, Упражнение 3.4g, стр. 72
17. Хопкрофт, Ульман (1979), Теорема 3.8, стр. 64; см. также Теорема 3.10, стр. 67
18. Ахо, Хопкрофт, Ульман (1974), Упражнение 10.14, стр.401
19. Ахо, Хопкрофт, Ульман (1974), Теорема 10.14, стр. 399
20. Хопкрофт, Ульман (1979), Теорема 13.15, стр.351
21. AR Meyer & LJ Stockmeyer (октябрь 1972 г.). Проблема эквивалентности для регулярных выражений с возведением в квадрат требует экспоненциального пространства (PDF) . 13-й ежегодный симпозиум IEEE по теории коммутации и автоматов. стр. 125–129.
22. LJ Stockmeyer; AR Meyer (1973). «Текстовые задачи, требующие экспоненциального времени». Труды 5-го ежегодного симпозиума по теории вычислений (STOC) (PDF) . ACM. стр. 1–9.
23. Хопкрофт, Ульман (1979), Следствие, стр. 353
24. Weyer, Mark (2002). «Разрешимость S1S и S2S». Автоматы, логика и бесконечные игры . Конспект лекций по информатике. Том 2500. Springer. С. 207–230. doi :10.1007/3-540-36387-4_12. ISBN 978-3-540-00388-5.
25. Ферст, Меррик; Сакс, Джеймс Б .; Сипсер, Майкл (1984). «Четность, схемы и иерархия полиномиального времени». Математическая теория систем . 17 (1): 13–27. doi :10.1007/BF01744431. MR  0738749. S2CID  14677270.
26. Кук, Стивен; Нгуен, Фуонг (2010). Логические основы сложности доказательства (1-е изд.). Итака, Нью-Йорк: Ассоциация символической логики. стр. 75. ISBN 978-0-521-51729-4.
27. J. Hartmanis, PL Lewis II и RE Stearns. Иерархии вычислений с ограниченной памятью. Труды 6-го ежегодного симпозиума IEEE по теории коммутационных схем и логическому проектированию , стр. 179–190. 1965.
28. «Как доказать, что язык не является регулярным?». cs.stackexchange.com . Получено 10 апреля 2018 г. .
29. Громкович, Юрай (2004). Теоретическая информатика: Введение в автоматы, вычислимость, сложность, алгоритмику, рандомизацию, связь и криптографию. Springer. С. 76–77. ISBN 3-540-14015-8. OCLC  53007120.
30. Конечный язык не следует путать с (обычно бесконечным) языком, генерируемым конечным автоматом.
31. Volker Diekert; Paul Gastin (2008). "First-order definible languages" (PDF) . В Jörg Flum; Erich Grädel; Thomas Wilke (ред.). Logic and automata: history and perspectives . Amsterdam University Press. ISBN 978-90-5356-576-6.
32. Honkala, Juha (1989). «Необходимое условие рациональности дзета-функции регулярного языка». Theor. Comput. Sci . 66 (3): 341–347. doi : 10.1016/0304-3975(89)90159-x . Zbl  0675.68034.
33. Флажоле и Седжвейк, раздел V.3.1, уравнение (13).
34. "Количество слов в регулярном языке $(00)^*$". cs.stackexchange.com . Получено 10 апреля 2018 г. .
35. «Доказательство теоремы для произвольных DFA».
36. "Количество слов заданной длины в регулярном языке". cs.stackexchange.com . Получено 10 апреля 2018 г. .
37. Флажоле и Седжвик (2002) Теорема V.3
38. Берстель, Жан; Ройтенауэр, Кристоф (1990). «Дзета-функции формальных языков». Пер. Являюсь. Математика. Соц . 321 (2): 533–546. CiteSeerX 10.1.1.309.3005 . doi : 10.1090/s0002-9947-1990-0998123-x. Збл  0797.68092. 
39. Берстель и Ройтенауэр (2011) стр.222
40. Сэмюэл Эйленберг. Автоматы, языки и машины . Academic Press.в двух томах «A» (1974, ISBN 9780080873749 ) и «B» (1976, ISBN 9780080873756 ), последний с двумя главами Брета Тилсона.  
41. Штраубинг, Ховард (1994). Конечные автоматы, формальная логика и сложность схем . Прогресс в теоретической информатике. Базель: Birkhäuser. стр. 8. ISBN 3-7643-3719-2. Збл  0816.68086.
42. Берстель и Ройтенауэр (2011) стр.47
43. Сакарович, Жак (2009). Элементы теории автоматов . Перевод с французского Рубена Томаса. Кембридж: Cambridge University Press . стр. 86. ISBN 978-0-521-84425-3. Збл  1188.68177.

Дальнейшее чтение

• Kleene, SC : Представление событий в нервных сетях и конечных автоматах. В: Shannon, CE, McCarthy, J. (ред.) Automata Studies, стр. 3–41. Princeton University Press, Princeton (1956); это слегка измененная версия его отчета RAND Corporation 1951 года с тем же названием, RM704.
• Сакарович, Дж. (1987). «Повторный взгляд на теорему Клини». Тенденции, методы и проблемы в теоретической информатике . Конспект лекций по информатике. Том 1987. С. 39–50. doi :10.1007/3540185356_29. ISBN 978-3-540-18535-2.

Внешние ссылки

• Сложность зоопарка : Класс REG