Детерминистский подход

Детерминистский подход основан на формальных грамматиках.

Формальная грамматика [15…19] представлена в виде

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

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

– конечное множество продукционных правил вида , ,

– начальный нетерминальный символ (буква).

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

Хомский определил четыре типа формальных грамматик [15]:

– автоматные;

– контекстно-свободные (бесконтекстные);

– контекстно-зависимые (непосредственно составляющих);

– без ограничений.

Для лексического анализа естественного языка и языка программирования используются автоматные грамматики. Для синтаксического анализа языка программирования используются контекстно-свободные грамматики. Для синтаксического анализа естественного языка обычно используются грамматики непосредственно-составляющих и без ограничений или эквивалентные им по мощности.

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