Грамматика с фразовой структурой

Грамматика с фразовой структурой — формальная грамматика, алгебраическая структура, состоящая из упорядоченной четвёрки G=(N, T, P, S) и определёной на ней неявно операцией конкатенации.

• N — конечное множество нетерминальных символов
• T — не пересекающееся с N конечное множество терминальных символов
• P — набор ограничивающих правил (продукций)

S — стартовый (начальный символ) Пример Грамматикой, порождающей язык {0n1n | n≥0}, является G: G= ({S}, {0,1}, P, S), где P = {S→0S1, S→ε}.

Понятие выводимости: Если αβγ последовательный набор символов языка G, а β→δ правило этого языка, то αβγ=>αδγ (αδγ непосредственно выводима из αβγ в G).

Цепь — последовательное присваивание нетерминальных символов.

Цикл — замкнутая цепь

x (x ∈ N) — недоступный символ, если x неэквивалентен стартовому символу S (x ≠ S) и не существует выводов типа S+→αxβ.

Символ называется непродуктивным, если не существует строки γ, такой, что нетерминальный символ не будет присвоен γ (x→γ)

Символ называется бесполезным если он непродуктивен или недоступен.

Источник: Википедия