Понятие порождающей грамматики

1.

2.

3.

Vt
- конечное множество терминальных
символов (терминальный символ — объект
формальной грамматики, имеющий в нём
конкретное неизменяемое значение и
являющийся элементом построения слов
данного языка)
Vn – конечное множество нетерменальных
символов (Нетерминал (нетерминальный
символ) — объект, обозначающий какуюлибо сущность языка (например: формула,
арифметическое выражение, команда) и не
имеющий конкретного символьного
значения.)

4.

Р – Конечное множество правил вывода (или
продукций), причем каждое правило этого
множества имеет вид: u→v, где
в общем случае uϵ(Vt ᴗ Vn)+ и vϵ(Vt ᴗ Vn)*
→ - символ непосредственной выводимости
S – аксиома грамматики. S ϵ Vn
Этот символ стоит в левой части первого
правила вывода из множества правил Р, с
которого начинается вывод любой цепочки.

5.

Для того чтобы различать терминальные и
нетерминальные символы, принято
обозначать терминальные символы
строчными буквами, а нетерминальные
заглавными буквами латинского алфавита.
Цепочки языка, порожденные грамматикой
G, состоят только из терминальных
символов. Нетерминальные символы
являются вспомогательными символами и
дают возможность рекурсивно порождать
бесконечное число цепочек языка.

6.

В грамматике G цепочка х непосредственно
порождает цепочку у, если x= αuβ, y= αvβ
и существует правило u → v ϵ P, т.е. цепочка
у непосредственно выводится из х.

7.

Языком, порождаемым грамматикой G=(Vt,
Vn, P,S), называется множество
терминальных цепочек х, выводимых в
грамматике G из аксиомы:
L(G) = {х|х ϵ Vt*; S=>х}
Где => - выводимость, т.е. цепочка х
выводится из аксиомы S за конечное число
шагов с использованием некоторой
совокупности правил вывода. Разделитель
“|” читается «такие, что»

8.

Пусть дана грамматика G=(Vt, Vn, P,S), в
которой Vt = {a,b}, Vn = {S}, P= {S →aSb, S →
ab}. Определить язык, порождаемый этой
грамматикой.

9.

Запишем вывод нескольких цепочек языка,
порождаемых данной грамматикой:
S → ab;
S → aSb → aabb;
S → aSb → aaSbb → aaabbb;
...
Запишем язык, порождаемый данной
грамматикой:
L(G) = {anbn|n>0}

10.

Язык включает цепочки, состоящие из
равного количества символов a и b, причем
символы b следуют за символом a.

11.

12.

Существуют следующие соглашения о
представлении порождающей грамматики:
1. Если множество правил вывода
грамматики приводится без специального
указания множеств терминальных и
нетерминальных символов, то грамматика
содержит только те терминальные и
нетерминальные символы, которые
встречаются в правилах вывода.

13.

2. Для наглядного представления множества P
все правила которые имеют одинаковые
левые части, записываются в одну строку с
с использованием разделителя «|»,
который в этом случае читается как союз
«или». Так, правила ввода из
рассмотренного примера можно записать
следующим образом: S → aSb | ab.