Регулярная грамматика — формальная грамматика типа 3 по иерархии Хомского, регулярные грамматики определяют в точности все регулярные языки, и поэтому эквивалентны конечным автоматам и регулярным выражениям. Регулярные грамматики являются подмножеством контекстно-свободных.
Задание набором правил Регулярная грамматика может быть задана набором правил как левая или правая регулярная грамматика.
Правая регулярная грамматика, или праволинейная грамматика, — все правила могут быть в одной из следующих форм: A → a A → aB A → εлевая регулярная грамматика, или леволинейная грамматика, — все правила могут быть в одной из следующих форм: A → a A → Ba A → ε
где заглавные буквы (A, B) обозначают нетерминалы из множества N строчные буквы (a, b) обозначают терминалы из множества Σ ε — пустая строка, то есть строка длины 0
Классы правых и левых регулярных грамматик эквивалентны — каждый в отдельности достаточен для задания всех регулярных языков. Любая регулярная грамматика может быть преобразована из левой в правую, и наоборот.
Альтернативные названия связаны с тем, что это подклассы более общего класса линейных грамматик.
Пример Правая регулярная грамматика G, заданная N = {S, A}, Σ = {a, b, c}, P состоит из следующих правил: S → aS S → bA A → ε A → cA и S является начальным символом. Эта грамматика описывает тот же язык, что и регулярное выражение a*bc*, то есть множество всех строк, состоящих из произвольного количества символов «a», за которыми следует один символ «b», а затем произвольное количество символов «c».
Ограниченность Существенно, что правила должны быть либо только лево-регулярными, либо только право-регулярными. Комбинация тех и других не допускается. Например, контекстно-свободный язык строк вида , где не является регулярным, но задается грамматикой G, где N = {S, A}, Σ = {a, b}, P состоит из правил S → aA A → Sb S → ε и S является начальным символом. Данная грамматика содержит одновременно лево-регулярные и право-регулярные правила, и следовательно не является регулярной.
См. также Регулярные выражения — в теории формальных языков Префиксная грамматика
Литература
Серебряков В. А., Галочкин М. П., Гончар Д. Р., Фуругян М. Г. Теория и реализация языков программирования — М.: МЗ-Пресс, 2006 г., 2-е изд. — ISBN 5-94073-094-9
Категория:Формальные грамматики