Разница между регулярным выражением и грамматикой в ​​автоматах

12

Я новичок в автоматах, и я получил краткое введение в регулярные выражения только вчера. Я прочитал различные правила для определения регулярного выражения. Но я не могу отличить регулярные выражения от грамматики языка (меня не учили грамматике регулярных выражений).

Я понимаю, что грамматика помогает нам генерировать допустимые строки в языке, но тогда это то, что правила для определения состояния регулярных выражений. Так в чем же разница? Я спросил своего профессора, и он сказал, что регулярные выражения - это самые основные строки в языке, а грамматика - это набор правил для любого языка, которые имеют более высокий порядок, чем регулярные выражения. Может ли кто-нибудь предоставить более подробную информацию?

Чару Бансал
источник

Ответы:

22

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

Основная причина того, что у нас есть все три, состоит в том, что они были созданы независимо, с первым набором эквивалентностей (есть также несколько других формализмов), доказанным Клини (этот результат или его часть называется теоремой Клини).

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

Конечно, иногда одну модель легче использовать для решения конкретной задачи, чем другую, из-за деталей формализма. Кроме того, то, как они работают в голове человека, часто немного отличается: конечные автоматы «чувствуют» себя как компьютеры, регулярные выражения «чувствуют», как будто вы строите строку из меньших подстрок, а регулярные грамматики «чувствуют» себя как более традиционная грамматика вывод или классификация предложения на языке (неудивительно, когда вы смотрите на историю).

Чтобы сравнить их, давайте определим их:

Регулярные выражения

Таким образом, регулярные выражения рекурсивно определены следующим образом:

  1. - это регулярное выражение
  2. ε - это регулярное выражение
  3. a является регулярным выражением для каждогоaΣ
  4. если и регулярные выражения, то AB
    • AB - это регулярное выражение (конкатенация)
    • AB - регулярное выражение (чередование)
    • A - регулярное выражение (звезда Клини)

Наряду с некоторой семантикой (то есть как мы интерпретируем операторы, чтобы получить строку), мы получаем способ генерации строк из обычного языка.

Обычные грамматики

Обычные грамматики состоят из четырех кортежей где - набор нетерминалов, - набор терминалов, - начальный нетерминал, а - набор из произведений, которые говорят нам, как шаг за шагом изменить начальный символ в строку в . может получать свои произведения из одного из двух типов (но не из обоих):(N,Σ,P,SN)NΣSPΣP

Правильные линейные грамматики

Для нетерминалов , , терминала и пустой строки все правила имеют вид:BCaε

  1. Ba
  2. BaC
  3. Bε

Левые линейные грамматики

Левый линейный грамматик являются одинаковыми, но править # 2 .BCa

Вдуматься

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

Грамматики, кажется, «помечают» разделы строки и группируют метки под новыми метками для проверки строки (т. Е. Если мы можем перейти от к строке или наоборот, мы счастливы).S

Однако они действительно делают одну и ту же фундаментальную вещь, и то, как вы видите метафору их функции, зависит от вас.

Люк Мэтисон
источник
Я бы больше акцентировал внимание на том факте, что грамматики генерируют строки в языке, в то время как регулярные выражения (как вы сказали) являются в большей степени подходящим шаблоном, который соответствует (или «проверяет») каждой строке в языке.
Ран Г.
@RanG., Это действительно обычный способ думать об этом, но вы можете перевернуть оба; анализ снизу вверх проверяет строку на соответствие грамматике, и вы можете использовать регулярное выражение в качестве компактного описания языка (хотя это, вероятно, менее распространено).
Люк Мэтисон
@simpleBob - множество нетерминалов, - начальный нетерминал. Что бы было? S RNSR
Люк Мэтисон
@ LukeMathieson Моя ошибка, я прочитал абзац и подумал, что это опечатка с буквой из-за порядка, в котором было определеноТеперь, когда я прочитал формальное определение в другом месте, кажется, что опечатка заключалась в том, что должно быть (я думаю) (Вторая строка в первом абзаце регулярных грамматик)R R PNRRP
Даниэль
@simpleBob, Ах да, это определенно опечатка. Благодарность!
Люк Мэтисон