A solvability condition for arbitrary formal grammars.pdf Продолжая исследование, начатое в работах [1, 2], рассмотрим систему полиномиальных уравнений Pj (z,x) = 0, Pj (0,0) = 0, j = 1,...,k, (1) которая решается относительно символов z = (z\\,... , zn) в виде ФСР, зависящих от символов x = (xi,... , xm). Такие системы имеют приложения в теории формальных языков, поскольку являются грамматиками, порождающими важные классы формальных языков: контекстно-свободных, языков непосредственно составляющих, языков в нормальной форме Грейбах и др. [3, 4]. В теории формальных языков символы x1,... , xm называются терминальными и образуют словарь (алфавит) данного языка, а символы z1,... ,zn называются нетерминальными и необходимы для задания грамматических правил. Над всеми символами определена некоммутативная операция умножения (конкатенации) и коммутативная операция формальной суммы, а также определена коммутативная операция умножения на комплексные числа, и потому можно рассматривать символьные многочлены и ФСР с числовыми (комплексными) коэффициентами. Наконец, мономы от терминальных символов интерпретируются как предложения языка, а каждый ФСР, который является решением системы (1), рассматривается как порождённый грамматикой формальный язык, т. е. формальная сумма всех «правильных» предложений этого языка [3, 4]. Исследовать решения символьных систем (1) достаточно трудно, поскольку некоммутативность умножения и отсутствие деления не дают возможности исключать неизвестные, и потому в работах [1,2] наряду с некоммутативной системой (1) рассмотрен её коммутативный образ, который получается в предположении, что все переменные, входящие в систему, принимают значения из поля комплексных чисел. Так, предположим, следуя [1], что все мономы от x1,... ,xm занумерованы в лексикографическом порядке по возрастанию степеней в последовательность u0,u1,..., играющую роль базиса, тогда каждый ряд s можно единственным образом записать в виде разложения по этому базису с числовыми коэффициентами (s,Ui) при мономах щ:

Скачать электронную версию публикации