Что такое регулярность?

Question

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

Когда я открыл для себя регулярные выражения и искал термин, я предположил, что это свойство «регулярности» относится к тому факту, что язык выражения имеет определяемый структурный шаблон.Однако, читая об этом предмете и лежащей в его основе теории, я узнал, что существуют языки, которые не являются регулярными, и тем не менее из того, как они определяются, становится ясно, что им можно сопоставить определенный шаблон.Одним из таких языков является (a^n)(b^n).Очевидно, что это образец, но это не обычный язык.Итак, теперь мне интересно, что такого в обычных языках, что делает их регулярными, а этот язык - нет?

Answer 1

Этимология названия взята из работы Клини 1950-х годов, описывающей обычные наборы используя свои математические обозначения, созданные для этой цели.Видеть этот.

Answer 2

Интуитивное объяснение информатики - это...сложный.Я попробую, но имейте в виду, что кое-что из этого будет «достаточно близким», но не теоретически строгим.

Регулярный язык — это язык, который может быть определен машиной, вычислительно эквивалентной конечному автомату (DFA/NDFA).Конечный автомат можно рассматривать как машину, которая работает исключительно в состояниях, без памяти.Итак, вы можете видеть, что^нб^н не может быть регулярным, поскольку для их сравнения требуется машина, которая может подсчитывать количество чисел a и b (и, следовательно, должна иметь бесконечную* емкость памяти).

Для сравнения (abc)^н является регулярно, поскольку количество повторений не имеет значения.

Для более строгого (и, соответственно, более плотного) представления проверьте статья в Википедии и связанные страницы.

_{*Бесконечность здесь не имеет значения, но я упоминаю ее для полноты картины.Возможно, было бы проще думать об этом как о «к счастью, всегда достаточно» памяти.}

Answer 3

Возможно, статья в Википедии о обычные языки может объяснить это лучше, чем мы.Тем не менее, я попробую.

С теоретической точки зрения регулярный язык (набор строк) — это язык, который можно сгенерировать с помощью конечный автомат.С точки зрения программиста, это эквивалентно утверждению, что его можно сгенерировать с помощью обычные выражения.Таким образом, все конечные языки (наборы строк) регулярны, но существуют и бесконечные языки, например^нб^н (язык всех строк из n a, за которыми следуют n b), который невозможно распознать с помощью FSA или регулярных выражений.Существуют более мощные вычислительные устройства (например, современные компьютеры, моделируемые с помощью Машины Тьюринга) который может распознавать эти языки.

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

Answer 4

Слово regular в regular expression относится к математической концепции регулярности, а не к английской концепции.Точно так же, как слово prime в математике имеют мало отношения к основной говядина.

Он унаследован CS (разделом математики) для обозначения более конкретной концепции: http://en.wikipedia.org/wiki/Regular_language

Answer 5

регулярные выражения не совсем регулярны, название этимологическое.