Что такое закономерность?

Question

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

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

Answer 1

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

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

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

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

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

Answer 2

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

Answer 3

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

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

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

Answer 4

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

Answer 5

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

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