|
91 2) для х и любой G С разрешим вопрос, принадлежит ли х языку L (G) или нет. Классы грамматик непосредственно составляющих, бесконтекстных и регулярных грамматик перечислимы, разрешимы и, как следствиедопу стимы [34]. Класс языков L (G) является идентифицируемым в определенных пределах, если для любой грамматики G Си любой полной информационной последовательности I (L (G)) существует алгоритм вывода D и такое т, что 1) Gt = GT при t > т, где Gt = D (St, С) и GT = D (St, С) и 2) L(GT) = L(G). Алгоритм D приближает грамматику G, если выполняются следующие два условия: (а) для любой цепочки х L (G) существует такое т, что при всех t > т х L (Gt), где Gt = D (St, С); (б) для любой грамматики G', такой, что L(G') — L (G) О, существует такое т, что Gt G' при всех t > т. D строго приближает G, если при выполнении условий (а) и (б) существует такая грамматика Н, что L (Н) = L (G) и Gt = Н для любого сколь угодно большого t. Алгоритм D можно использовать для идентификации грамматики G, если он восстанавливает только одну грамматику, и эта грамматика порождает в точности язык L (G). Для этого необходимо, чтобы алгоритм D в конечном счете осуществлял эффективный выбор одной грамматики и прекращал рассмотрение новых данных после этого выбора. Если относительно алгоритма D можно гарантировать только, что в конце концов он отвергнет любую грамматику, не порождающую языка L (G), то язык L (G) достижим. _______ |
99 языка L(G) является структурно полным, если для любого правила подстановки из грамматики G существует хотя бы одна цепочка из St, при построении которой было использовано это правило. Пусть ze у*. Тогда k-окончание цепочки z по отношению к множеству 5е2Гг это множество g (z, S, к) вида g(z, S, к) = {х е z x e S' и x < k}, где lx \ — длина цепочки x, ak> 0. Если такой цепочки x e у*, чтобы zx e S и x < k, не существует, то множество g (z, S, к) считается неопределенным. Пусть функция f преобразует множество вспомогательных символов грамматики G2 в множество вспомогательных символов грамматики Gj. Кроме того, функция f преобразует начальный вспомогательный символ грамматики G2 в начальный вспомогательный символ грамматики G) и правила подстановки G2 в правила подстановки Gt. Если такая функция существует, то грамматика G; покрывает грамматику G2, причем L (G2) с L (GO [125]. Грамматика Gt является совместимой с образцом языка St, если L (GJ содержит все цепочки из положительной части и не содержит ни одной цепочки из отрицательной части образца. Класс С грамматик является допустимым, если: 1) он перечислим; 2) для х е у* и любой G е С разрешим вопрос, принадлежит ли х языку L (G) или нет. Классы грамматик непосредственно составляющих, бесконтекстных и регулярных грамматик перечислимы, разрешимы и, как следствиедопустимы. Класс языков L (G) является идентифицируемым в определенных пределах, если для любой грамматики G е Си любой полной 100 информационной последовательности I (L (G)) существует алгоритм вывода D и такое т, что 1) = Gt при t > т, где Gt = D (St, С) и Gt = D (St, С) и 2) L(GT) = L(G). Алгоритм D приближает грамматику G, если выполняются следующие два условия: (а) для любой цепочки хе L (G) существует такое т, что при всех t > т х е L (Gt), где Gt = D (S,, С); (б) для любой грамматики G', такой, что L(G') — L (G) ^0, существует такое т, что G, *G' при всех t > т. D строго приближает G, если при выполнении условий (а) и (б) существует такая грамматика Н, что L (Н) = L (G) и Gt = Н для любого сколь угодно большого t. Алгоритм D можно использовать для идентификации грамматики G, если он восстанавливает только одну грамматику, и эта грамматика порождает в точности язык L (G). Для этого необходимо, чтобы алгоритм D в конечном счете осуществлял эффективный выбор одной грамматики и прекращал рассмотрение новых данных после этого выбора. Если относительно алгоритма D можно гарантировать только, что в конце концов он отвергнет любую грамматику, не порождающую языка L (G), то язык L (G) достижим. Бесконтекстная грамматика G = (Vn, Vt, Р, S) является вполне редуцированной [119], если: 1) для любого A е Vn — S множество Р не содержит ни одного правила подстановки типа А -»Л ; 2) для любых А, В е Vn множество Р не содержит ни одного правила типа А ->В; 3) если S 2. а, а е (VN U Vt)*, то существует цепочка хе у* , |