Регулярные выражения, регулярные грамматики и конечные автоматы - это просто три разных формализма для одной и той же вещи. Существуют алгоритмы для преобразования из любого из них в любой другой.
Основная причина того, что у нас есть все три, состоит в том, что они были созданы независимо, с первым набором эквивалентностей (есть также несколько других формализмов), доказанным Клини (этот результат или его часть называется теоремой Клини).
Таким образом, в этом контексте, в зависимости от того, в какую сторону вы хотите запустить модели, все они распознают или генерируют строки обычного языка, и математически в этом смысле нет никакой разницы.
Конечно, иногда одну модель легче использовать для решения конкретной задачи, чем другую, из-за деталей формализма. Кроме того, то, как они работают в голове человека, часто немного отличается: конечные автоматы «чувствуют» себя как компьютеры, регулярные выражения «чувствуют», как будто вы строите строку из меньших подстрок, а регулярные грамматики «чувствуют» себя как более традиционная грамматика вывод или классификация предложения на языке (неудивительно, когда вы смотрите на историю).
Чтобы сравнить их, давайте определим их:
Регулярные выражения
Таким образом, регулярные выражения рекурсивно определены следующим образом:
- ∅ - это регулярное выражение
- ε - это регулярное выражение
- a является регулярным выражением для каждогоa∈Σ
- если и регулярные выражения, то
AB
- A⋅B - это регулярное выражение (конкатенация)
- A∣B - регулярное выражение (чередование)
- A∗ - регулярное выражение (звезда Клини)
Наряду с некоторой семантикой (то есть как мы интерпретируем операторы, чтобы получить строку), мы получаем способ генерации строк из обычного языка.
Обычные грамматики
Обычные грамматики состоят из четырех кортежей где - набор нетерминалов, - набор терминалов, - начальный нетерминал, а - набор из произведений, которые говорят нам, как шаг за шагом изменить начальный символ в строку в . может получать свои произведения из одного из двух типов (но не из обоих):(N,Σ,P,S∈N)NΣSPΣ∗P
Правильные линейные грамматики
Для нетерминалов , , терминала и пустой строки все правила имеют вид:BCaε
- B→a
- B→aC
- B→ε
Левые линейные грамматики
Левый линейный грамматик являются одинаковыми, но править # 2 .B→Ca
Вдуматься
Так что, взглянув на эти определения и поиграв с ними, мы увидим, что регулярные выражения выглядят как соответствующие правила или способы последовательного обращения со строками.
Грамматики, кажется, «помечают» разделы строки и группируют метки под новыми метками для проверки строки (т. Е. Если мы можем перейти от к строке или наоборот, мы счастливы).S
Однако они действительно делают одну и ту же фундаментальную вещь, и то, как вы видите метафору их функции, зависит от вас.