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

Материал из Википедии — свободной энциклопедии

В информатике, регулярная грамматика — формальная грамматика типа 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 i b i$ задается грамматикой G, где N = {S, A}, Σ = {a, b}, P состоит из правил

S → aA

A → Sb

S → ε

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