|
92 Бесконтекстная грамматика G = (VN, VT, Р, S) является вполне редуцированной [119], если: 1) для любого A VN — S множество Р не содержит ни одно-то правила подстановки типа А ; 2) для любых А, В VN множество Р не содержит ни одного правила типа А В; 3) если S a, a (VN U VT)*, то существует цепочка х , такая, что а х; 4) каждое правило использовано при порождении хотя бы одной цепочки из L (G). Пусть G = (VN, VT, Р, S) — вполне редуцированная бесконтекстная грамматика. Структурной информационной последовательностью Is (L) языка L (G) является последовательность цепочек из множества !+уу L([G])}U{-yy ( VT U{[,]})*-L([G])}. Пусть G — вполне редуцированная бесконтекстная грамматика. Положительная структурная информационная последовательность (L (G)) является полной, если каждая цепочка из L ([G]) входит в (L (G)) хотя бы однажды. Пусть х — непустая цепочка над F = VN U VT . Для грамматики G = (VN, VT, Р, S) самым левым и самым правым множествами основных символов цепочки х называются множества Lt(x)={ax аа или(х А и a Lt (А))}, Rt (х) = {а х аа или (х А и a Rt (А))}, где a VT, A VN и а V*. В данном случае Lt (х) (Rt (х)) состоит из самых левых (самых правых) основных символов в некотором выводе цепочки х. Пусть G = (VN, FT, Р, S) — вполне редуцированная бесконтекстная грамматика. Левый и правый профили порядка к цепочки х из (VN U Vt U {[3,34]}) определяют следующий образом [69]л Полагают V Т=УТ U |
101 1 l'r такая, что a =^> x; 4) каждое правило использовано при порождении хотя бы одной цепочки из L (G). Пусть G = (VN, VT, Р, S) — вполне редуцированная бесконтекстная грамматика. Структурной информационной последовательностью Is (L) языка L (G) является последовательность цепочек из множества !+yly eL([G])}U{-yy е( VT U{[,]})*-L([G])}. Пусть G — вполне редуцированная бесконтекстная грамматика. Положительная структурная информационная последовательность Ps (L (G)) является полной, если каждая цепочка из L ([G]) входит в Ps (L (G)) хотя бы однажды. Пусть х — непустая цепочка над F = Vn U Vt . Для грамматики G = (VN, VT, Р, S) самым левым и самым правым множествами основных символов цепочки х называются множества Lt (х) = {а I х => аа или (х=>А/У и ае Lt (А))}, G G ♦ * Rt (х) = {а х аа или (х^>/?А и ае Rt (А))}, где aeVT, yleVw и a/?eV*. В данном случае Lt (х) (Rt (х)) состоит из самых левых (самых правых) основных символов в некотором выводе цепочки х. Пусть G = (Vn, Ft, Р, S) — вполне редуцированная бесконтекстная грамматика. Левый и правый профили порядка к цепочки х из (Vn U Vt U {[,]})+ определяют следующим образом [12]. Полагают V’t=Vt U {[,]}. Тогда , /Ир У к >есл ujnLk(x) = {и I ^т,и=) Rt(.x) = {u\x^yi...ym,y, , где $eV’T. (3.1) (3.2) |