Что такое регулярность?
Это - больше вопроса об информатике, чем программирующий, но я полагаю, что это - лучшее место из всех связанных сайтов для выяснения у этого.
Когда я обнаружил Регулярные выражения и искал термин, я предположил, что это свойство "регулярности" относится к тому, что язык выражения имеет определимый структурный шаблон. Однако в чтении о предмете и теории позади этого я узнал, что существуют виды языков, которые не являются регулярными, и все же от способа, которым они определяются, ясно, что шаблон может быть подобран им. Один такой язык (a^n) (b^n). Очевидно это - шаблон, и все же это не регулярный язык. Таким образом, теперь меня оставляют, задаваясь вопросом, что о регулярных языках делает их регулярными, и этот язык нет?
5 ответов
] Этимология названия происходит из работы Клена 1950-х годов, описывающей [] обычные множества[], используя его математическую нотацию, созданную для этой цели. See []this[].[
]] Интуитивное объяснение компьютерной науки - это... хитро. Я попробую, но имейте в виду, что некоторые из них будут "достаточно близки", но не теоретически строгими.[
] []Обычный язык - это язык, который может быть решен машиной, являющейся вычислительным эквивалентом конечных автоматов (DFA/NDFA). Конечные автоматы можно представить как машину, которая работает только в состояниях, без хранения. Таким образом, вы можете видеть, что a[]n[]b[]n[] не может быть обычной, так как для сравнения требуется машина, которая может считать число a's и b's (и, таким образом, должна иметь бесконечный* объем памяти). [
] []Для сравнения, (abc)[]n[] []is[] regular, потому что количество повторений не имеет значения.[
] []Для более строгого (и соответственно более плотного) просмотра проверьте статью в википедии []n[] и связанные с ней страницы.[
] [][]*В этом случае бесконечность не имеет значения, но я упоминаю о ней для полноты. Может быть проще считать это "к счастью, всегда достаточно" хранилищем.[][
]Регулярные выражения не совсем регулярные, имя этимологическое.
Возможно, статья Википедии на обычных языках может объяснить это лучше, чем мы можем. Однако, я попробую.
С теоретической точки зрения обычный язык (набор строк) - это такой язык, который может быть сгенерирован с помощью автомата конечных состояний . В терминах программиста это эквивалентно тому, что он может быть сгенерирован с помощью регулярных выражений . Таким образом, все конечные языки (наборы строк) являются регулярными, но существуют некоторые бесконечные языки, такие какnbn (язык всех строк n a, за которыми следуют n b), которые не могут быть распознаны ни с помощью FSA, ни с помощью регулярных выражений. Существуют более мощные вычислительные устройства (такие как современные компьютеры, которые моделируются с использованием Turing Machines), которые могут распознавать эти языки.
Причина, по которой регулярные выражения так часто используются в программировании для поиска строк, заключается в том, что они могут распознавать подавляющее большинство важных для нас, программистов, строк, и в то же время могут быть реализованы для быстрого поиска очень с использованием автоматов конечных состояний.
Слово Регулярное в Регулярное выражение относится к математической концепции регулярных, а не английской концепции. Как правило, как слово Prime в математике медведь мало отношения к Prime говядина.
Он унаследован CS (который является отделением математики) для обозначения более конкретной концепции: http://en.wikipedia.org/wiki/regular_language