60. Теория формальных грамматик. Основные понятия и положения. Применение в информатике.

Теория формальных грамматик - раздел математической лингвистики, включающий способы описания формальных грамматик языков, построение методов и алгоритмов анализа принадлежности цепочек языку, а также алгоритмов перевода (трансляции) алгоритмических языков на язык машины.

Основные определения теории формальных грамматик

Словарь (алфавит)(V) – конечное непустое множество символов (элементов). Элементы – буквы, слова, образы, математические знаки и др.

Морфема– элементарная единица слова.

Цепочка w (предложение) – конечная последовательность символов. Цепочки образуются с помощью конкатенаций (объединений). |w| - длина цепочки.

Язык над данным алфавитом – произвольное (возможно, бесконечное) множество предложений в этом алфавите.

Формальная грамматика – это четверка G = (VT, VN, P, S), где:

VT – алфавит терминальных (основных) символов, из этих символов строятся языковые цепочки;

VN – алфавит нетерминальных (вспомогательных) символов, конечное непустое множество, вспомогательные символы обозначают классы слов или словосочетаний, причем

VN ∩ VT = Æ; VN È VT = V – алфавит грамматики G;

P – множество правил подстановки (или продукций);

S – начальный/корневой символ (цель грамматики, аксиома), выделенный нетерминальный символ, который означает класс языковых объектов, для которых предназначена данная грамматика, SÎVN.

Длина вывода – число применений правил вывода.

Законченный вывод цепочки – не существуют никакой другой, выводимой из неё.

Основные определения теории формальных грамматик (продолжение)

V* – все возможные цепочки символов (предложения) алфавита V.

V+ – множество V*\{Λ, где Λ – пустая цепочка).

Правило подстановки (элемент множества P) будет иметь вид:

α → β, где α Î V+, β Î V*,

причем хотя бы один символ предложения α должен быть нетерминальным.

В любом предложении вхождение цепочки символов α может быть заменено цепочкой β:

("γ, δ Î V*) γαδ Þ γβδ

В этом случае говорят, что β выводима из α.

Символ «→» применяется при записи правил вывода.

Символ «Þ» используется для обозначения возможности вывода одного предложения из другого в результате применения некоторого количества (одного или нескольких) правил грамматики.

Вывод в грамматике начинается с корневого символа S и заключается в последовательном применении правил подстановки.

Предложение называется терминальным, если оно состоит только из терминальных символов.

Γ(G) – язык, порождаемый грамматикой G и содержащий все терминальные предложения (и только их), выводимые из начального символа S:

Γ(G) = {α| (α Î VT*) & (S Þ α)}

Виды формальных грамматик

Распознающие – для любой распознаваемой цепочки она решает, является ли эта цепочка правильной с точки зрения конкретного языка.

Порождающие– может построить любую правильную цепочку.

Преобразующие– для любой правильной цепочки строит её отображение в виде правильной цепочки.