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

---

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

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

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

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

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

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

---