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

В інформатики, регулярна граматика - формальна граматика типу 3 по ієрархії Хомського. Регулярні граматики визначають в точності всі регулярні мови, і тому еквівалентні кінцевим автоматам і регулярними виразами. Регулярні граматики є підмножиною контекстно-вільних.


1. Завдання набором правил

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

права регулярна граматика - все правила можуть бути в одній з наступних форм:

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

ліва регулярна граматика - все правила можуть бути в одній з наступних форм:

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

де

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

Класи правих і лівих регулярних граматик еквівалентні - кожен окремо достатній для завдання всіх регулярних мов. Будь-яка регулярна граматика може бути перетворена з лівої в праву, і навпаки.


1.1. Приклад

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

S → aS
S → bA
A → ε
A → cA

і S є початковим символом. Ця граматика описує ту ж мову, що й регулярний вираз a * bc *.

2. Обмеженість

Будь контекстно-вільна граматика може бути легко перетворена в вид, в якому правила складаються тільки з ліво-регулярних або право-регулярних (для контекстно-вільних граматик допустимо наявність тих і інших одночасно). Отже, такі граматики можуть висловити всі контекстно-вільні мови. Регулярні граматики можуть містити або ліво-регулярні правила, або право-регулярні, але не обидва види одночасно. Тому вони можуть описати лише підмножина мов, званих регулярними мовами.

Наприклад, контекстно-вільна мова рядків виду a i b i, i ≥ 0 задається граматикою G, де N = {S, A}, Σ = {a, b}, P складається з правил

S → aA
A → Sb
S → ε

і S є початковим символом. Зверніть увагу на те, що дана граматика містить одночасно ліво-регулярні і право-регулярні правила, і отже не є регулярною.


Література

  • Робін Хантер Основні концепції компіляторів = The Essence of Compilers. - М .: "Вильямс", 2002. - С. 256. - ISBN 5-8459-0360-2