Тема 2: Регулярные граматики
Определение: Регулярная грамматика это грамматика 3-го типа по Хомскому. Она также состоит из четвёрки G=(VT, VN, P, S), VN∩VТ=∅ где:
· VТ - терминальный алфавит.
· VN - нетерминальный алфавит.
- P - множество правил или продукций. Любое правило в регулярных грамматиках имеет следующий общий вид: A->a или A->bC, где a, bÎVT; A, CÎVN. S - начальный символ из набора нетерминалов, аксиома.
Регулярная грамматика может быть задана набором правил как левая или правая регулярная грамматика.
Определение: Правая регулярная грамматика – все правила могут быть в одной из следующих форм: A->a или A->bC, где a, bÎVT; A,CÎVN.
Пример правой регулярной грамматики: G=(VT, VN, P, S), VT = {0,1}, VN = {S, A}, P = {1.S->1, 2.S->0, 3.S-> 1A, 4.S-> 0S, 5.A-> 0S, 6.A->0}.
Определение: Левая регулярная грамматика – все правила могут быть в одной из следующих форм: A->a или A->Cb, где a, bÎVT; A,CÎVN.
Пример правой регулярной грамматики: G=(VT, VN, P, S), VT = {a, b}, VN = {S, T, R}, P = {1.S->Ta, 2.T->Ta, 3.T-> Rb, 4.R-> Rb, 5.R->b}.
Классы правых и левых регулярных грамматик эквивалентны. Любая регулярная грамматика может быть преобразована из левой в правую, и наоборот. Регулярные грамматики могут содержать либо лево-регулярные правила, либо право-регулярные – но не оба вида одновременно. Следующая грамматика не является регулярной:
G=(VT, VN, P, S), VT = {a, b}, VN = { S, A}, P = {1.S->aA, 2.A->Sb,
3.S-> a, 4.A->b}.
Основные порталы (построено редакторами)