Cтраница 4
Внимательное наблюдение за деревом, показанном на рис. 8.2.4, обнаруживает, что структура повторяет себя после третьего такта. Правый столбец выходных троек бит распадается на две одинаковые совокупности по 8 троек. Это значит, трехбитовые выходные последовательности на каждом такте определяются входным битом и двумя предыдущими входными битами, т.е. двумя битами, содержащимися в первых двух ячейках регистра сдвига. Бит в последней ячейке регистра сдвига перемещается направо ( покидает регистр) и не влияет больше на выход. Теперь видим, что все ветви, исходящие из двух узлов с одинаковой меткой ( одинаковым состоянием) являются идентичными в том смысле, что они генерируют одинаковые выходные последовательности. Это означает, что два узла, имеющие одинаковую метку, можно слить. Если мы это сделаем в дереве, показанном на рис. 8.2.4, мы получим другую диаграмму, которая более компактна, именно получим решетку. [46]
Обычно исходная программа на Фортране записывается на специальных бланках, аналогичных представленным на рис. 12.1. Предложение на Фортране, или, как часто говорят, оператор Фортрана, занимает колонки с 7 - й по 72 - ю включительно. Для того чтобы можно было ссылаться на предложения, им могут присваиваться номера. Номера предложений, или, иными словами, метки - это целые числа без знака, содержащие не более пяти цифр и лежащие в диапазоне значений от 00001 до 99999 включительно. Обычно левые незначащие нули не записываются и заменяются пробелами, поэтому записи вида 00123 и 123 считаются идентичными. Метки могут присваиваться в любом порядке, однако никакие два предложения не должны иметь одинаковых меток. [47]
Внимательное наблюдение за деревом, показанном на рис. 8.2.4, обнаруживает, что структура повторяет себя после третьего такта. Правый столбец выходных троек бит распадается на две одинаковые совокупности по 8 троек. Это значит, трехбитовые выходные последовательности на каждом такте определяются входным битом и двумя предыдущими входными битами, т.е. двумя битами, содержащимися в первых двух ячейках регистра сдвига. Бит в последней ячейке регистра сдвига перемещается направо ( покидает регистр) и не влияет больше на выход. Теперь видим, что все ветви, исходящие из двух узлов с одинаковой меткой ( одинаковым состоянием) являются идентичными в том смысле, что они генерируют одинаковые выходные последовательности. Это означает, что два узла, имеющие одинаковую метку, можно слить. Если мы это сделаем в дереве, показанном на рис. 8.2.4, мы получим другую диаграмму, которая более компактна, именно получим решетку. [48]
Множество С отрезков цепочки х называется системой составляющих этой цепочки, если оно удовлетворяет двум условиям: 1) множество С содержит отрезок, состоящий из всех точек цепочки х, и все одноточечные отрезки х: 2 любые два отрезка из С либо не пересекаются, либо один из них содержится в другом. Элементы С называются составляющими. Одноточечные отрезки называются точечными ( тривиальными) составляющими. При описании предложений естественного языка с помощью системы составляющих обычно используют размеченную систему составляющих, т.е. тройку ( С. Здесь цепочка х имеет вид agbacdef. Для наглядного изображения системы составляющих будем заключать каждую нетривиальную составляющую в скобки, причем левую и правую скобки, отвечающие одной составляющей, будем помечать одинаковой меткой так, чтобы разные пары скобок были помечены разными метками. [49]