Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Формальный язык, который может быть описан с помощью регулярного выражения, и естественный язык, которому присущи закономерности.
Formal language that can be expressed using a regular expression
natural language that is regulated
В теоретической информатике и теории формальных языков, регулярный язык (также называемый рациональным языком) назван в честь американского математика Стивена Коула Клини. В иерархии Чомского, регулярные языки – это языки, порождаемые грамматиками 3-го типа.
In theoretical computer science and formal language theory, a regular language (also called a rational language) (after American mathematician Stephen Cole Kleene). In the Chomsky hierarchy, regular languages are the languages generated by Type 3 grammars.
Примеры
Все конечные языки регулярны; в частности, язык пустой строки {ε} = Ø* является регулярным. Другие типичные примеры включают язык, состоящий из всех строк над алфавитом {a, b}, которые содержат четное число символов 'a', или язык, состоящий из всех строк вида: несколько символов 'a', за которыми следуют несколько символов 'b'. Простым примером языка, который не является регулярным, является множество строк {anbn | n ≥ 0}. Интуитивно, его нельзя распознать с помощью конечного автомата, поскольку конечный автомат обладает конечной памятью и не может запомнить точное количество символов 'a'. Методы строгого доказательства этого факта приведены ниже.
All finite languages are regular; in particular the empty string language {ε} = Ø* is regular. Other typical examples include the language consisting of all strings over the alphabet {a, b} which contain an even number of a's, or the language consisting of all strings of the form: several a's followed by several b's. A simple example of a language that is not regular is the set of strings {anbn | n ≥ 0}. Intuitively, it cannot be recognized with a finite automaton, since a finite automaton has finite memory and it cannot remember the exact number of a's. Techniques to prove this fact rigorously are given below.
Результаты сложности
В теории вычислительной сложности класс сложности всех регулярных языков иногда называют REGULAR или REG и равен DSPACE(O(1)) – классу задач принятия решений, которые могут быть решены в постоянном объеме памяти (объем используемой памяти не зависит от размера входных данных). REGULAR ≠ AC0, поскольку он (тривиально) содержит задачу определения четности/нечетности числа единиц во входных данных, и эта задача не принадлежит классу AC0. С другой стороны, REGULAR не включает AC0, так как нерегулярный язык палиндромов или другой нерегулярный язык могут быть распознаны в AC0. Если язык не является регулярным, для его распознавания требуется машина с объемом памяти не менее Ω(log log n) (где n – размер входных данных). Иными словами, DSPACE(o(log log n)) равен классу регулярных языков. На практике большинство нерегулярных задач решаются машинами, использующими как минимум логарифмический объем памяти.
In computational complexity theory, the complexity class of all regular languages is sometimes referred to as REGULAR or REG and equals DSPACE(O(1)), the decision problems that can be solved in constant space (the space used is independent of the input size). REGULAR ≠ AC0, since it (trivially) contains the parity problem of determining whether the number of 1 bits in the input is even or odd and this problem is not in AC0. On the other hand, REGULAR does not contain AC0, because the nonregular language of palindromes, or the nonregular language can both be recognized in AC0. If a language is not regular, it requires a machine with at least Ω(log log n) space to recognize (where n is the input size). In other words, DSPACE(o(log log n)) equals the class of regular languages. In practice, most nonregular problems are solved by machines taking at least logarithmic space.
Обобщения
Понятие регулярного языка было обобщено на бесконечные слова (см. ω-автоматы) и на деревья (см. автоматы на деревьях). Рациональное множество обобщает понятие (регулярного/рационального языка) на моноиды, которые не обязательно свободны. Аналогично, понятие распознаваемого языка (конечным автоматом) имеет аналог в виде распознаваемого множества над моноидом, который не обязательно свободен. Говард Штраубинг отмечает в связи с этим, что термин "регулярный язык" несколько неудачен. В работах, испытавших влияние монографии Эйленберга, часто используется термин "распознаваемый язык", относящийся к поведению автоматов, или "рациональный язык", относящийся к важным аналогиям между регулярными выражениями и рациональными степенными рядами. (Фактически, Эйленберг определяет рациональные и распознаваемые подмножества произвольных моноидов; эти два понятия, как правило, не совпадают.) Эта терминология, хотя и более обоснованная, не получила широкого распространения, и "регулярный язык" используется практически повсеместно.
The notion of a regular language has been generalized to infinite words (see ω automata) and to trees (see tree automaton). Rational set generalizes the notion (of regular/rational language) to monoids that are not necessarily free. Likewise, the notion of a recognizable language (by a finite automaton) has namesake as recognizable set over a monoid that is not necessarily free. Howard Straubing notes in relation to these facts that “The term "regular language" is a bit unfortunate. Papers influenced by Eilenberg's monograph often use either the term "recognizable language", which refers to the behavior of automata, or "rational language", which refers to important analogies between regular expressions and rational power series. (In fact, Eilenberg defines rational and recognizable subsets of arbitrary monoids; the two notions do not, in general, coincide.) This terminology, while better motivated, never really caught on, and "regular language" is used almost universally.”
Рациональные ряды – это еще одно обобщение, на этот раз в контексте формального степенного ряда над полукольцом. Этот подход приводит к взвешенным рациональным выражениям и взвешенным автоматам. В этом алгебраическом контексте регулярные языки (соответствующие булевым взвешенным рациональным выражениям) обычно называют рациональными языками. Также в этом контексте теорема Клини находит обобщение, известное как теорема Клине — Шютценбергера.
Rational series is another generalization, this time in the context of a formal power series over a semiring. This approach gives rise to weighted rational expressions and weighted automata. In this algebraic context, the regular languages (corresponding to Boolean weighted rational expressions) are usually called rational languages. Also in this context, Kleene's theorem finds a generalization called the Kleene Schützenberger theorem.