Регулярная грамматика кратко

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

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

Задание набором правил

Регулярная грамматика может быть задана набором правил как левая или правая регулярная грамматика.

Правая регулярная грамматика, или праволинейная грамматика, — все правила могут быть в одной из следующих форм:

1. A → a
2. A → aB
3. A → ε

левая регулярная грамматика, или леволинейная грамматика, — все правила могут быть в одной из следующих форм:

1. A → a
2. A → Ba
3. A → ε

где

• заглавные буквы (A, B) обозначают нетерминалы из множества N
• строчные буквы (a, b) обозначают терминалы из множества Σ
• ε — пустая строка, то есть строка длины 0

Классы правых и левых регулярных грамматик эквивалентны — каждый в отдельности достаточен для задания всех регулярных языков. Об этом говорит сайт https://intellect.icu . Любая регулярная грамматика может быть преобразована из левой в правую, и наоборот.

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

Пример

Правая регулярная грамматика G, заданная N = {S, A}, Σ = {a, b, c}, P состоит из следующих правил:

S → aS

S → bA

A → ε

A → cA

и S является начальным символом. Эта грамматика описывает тот же язык, что и регулярное выражение a*bc*.

Ограниченность

Существенно, что правила должны быть либо только лево-регулярными, либо только право-регулярными. Комбинация тех и других не допускается. Например, контекстно-свободный язык строк вида , где не является регулярным, но задается грамматикой G, где N = {S, A}, Σ = {a, b}, P состоит из правил

S → aA

A → Sb

S → ε

и S является начальным символом. Данная грамматика содержит одновременно лево-регулярные и право-регулярные правила, и следовательно не является регулярной.

Вау!! 😲 Ты еще не читал? Это зря!

• Регулярные выражения — в теории формальных языков
• Префиксная грамматика

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