Меню
Главная
Случайная статья
Настройки
|
Регулярная грамматика — формальная грамматика типа 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*.
Ограниченность
Существенно, что правила должны быть либо только лево-регулярными, либо только право-регулярными. Комбинация тех и других не допускается.
Например, контекстно-свободный язык строк вида , где не является регулярным, но задается грамматикой G, где N = {S, A}, = {a, b}, P состоит из правил
- S aA
- A Sb
- S
и S является начальным символом. Данная грамматика содержит одновременно лево-регулярные и право-регулярные правила, и следовательно не является регулярной.
См. также
Литература
|
|