Любая цепочка

Cтраница 3

Однако суть дела в том, что порождению естественно противопоставляется не распознавание, а, так сказать, допускание. Именно естественно говорить, что некоторая грамматика G допускает язык L, если G дает процедуру, способную для любой цепочки х е L рано или поздно установить это. [31]

Схема последовательного соединения звеньев. [32]

Таким образом, передаточная функция данной системы равна произведению передаточных функций ее звеньев. Нетрудно видеть, что это положение, доказанное ранее для системы, состоящей из двух звеньев, справедливо для любой цепочки последовательно соединенных звеньев. [33]

Затем среди всех этих выводов берется максимальный. Другими словами, те ( я) - это такое число шагов, которое, с одной стороны, заведомо достаточно для вывода любой цепочки не длиннее п, а с другой стороны - необходимо, так как среди выводимых цепочек не длиннее п имеется хотя бы одна цепочка, которую нельзя вывести меньше чем за fa ( n) шагов. [34]

Было бы ошибкой, если бы от критерия III осталось впечатление, что здесь чрезвычайно важно рассматривать именно верхние подматрицы Ak. Или мы могли бы использовать любую цепочку главных подматриц, начиная с произвольного диагонального элемента а - / в качестве первой подматрицы, и добавляя каждый раз необходимые элементы из новой строки и нового столбца с одинаковыми номерами. [35]

Однако абстрактные недетерминированные машины такого типа обладают волшебным свойством: если существует выбор, они всегда избирают правильный переход, т.е. переход, ведущий к допущению входной цепочки при наличии такого перехода. Автомат на рис. 4.3, например, допускает цепочки ab и aabaab, но отвергает цепочки abb и abba. Легко видеть, что этот автомат допускает любые цепочки, оканчивающиеся на ab и отвергает все остальные. [36]

Важнее для внутренней работы языка тот факт, что любая непустая цепочка может использоваться как переменная. Некоторые обычные переменные явно входят в исходную программу. Косвенная ссылка дает возможность использовать в качестве переменной любую цепочку, и в частности присвоить ей значение. [37]

Если индекс / равен i - 1 ( k может быть произвольным), то мы назовем i - й шаг линейным. X ( flj-i) l; поэтому длина г любой цепочки ( 11) равняется Х ( п) плюс число малых шагов. [38]

Имеется несколько функций со значениями типа образец. Результатом ЬЕМ ( целое) является образец, успешно сопоставляющийся с любой цепочкой указанной длины. [39]

Ниже перечислены функции Трака в активной записи, но все они могут - вызываться также и в нейтральном режиме. У функции всегда есть значение в виде цепочки, однако функциям не возбраняется выдать в качестве значения пустую цепочку; в особенности это имеет смысл для тех функций, результат которых выражается в побочных эффектах. Каждый бланк состоит из трех частей: мени бланка, в качестве которого может выступать любая цепочка, тела бланка, которое тоже может быть любой цепочкой, и указателя - бланка, первоначально указывающего на позицию непосредственно перед первой литерой тела бланка. [40]

Если Р и Q - два образца, то конкатенация Р и Q, записываемая Р Q, есть новый образец, который сопоставляется с любой цепочкой, которая начинается с подцепочки, сопоставляемой с Р, причем остаток цепочки сопоставляется с Q. Альтернативное объединение Р и Q, записываемое P Q это образец, который сопоставляется с любой цепочкой, сопоставляющейся с Р или с Q. Для таких составных образцов важен порядок сопоставления. В случае альтернативного объединения P Q действует следующее правило: сначала проверяются все альтернативы для Р в текущем положении указателя CURSOR, а затем проверяются все альтернативы для Q. Для конкатенации Р Q действия происходят в таком порядке: найти одно соответствие для Р в текущем положении указателя CURSOR, переместить CURSOR в конец сопоставленной подцепочки, а затем попытаться сопоставить образец Q, начиная с нового положения CURSOR. Если такая подцепочка найдена, переместить CURSOR и вновь попробовать Q; если же нет, то сопоставление с конкатенацией образцов оканчивается неудачей. [42]

За любым из приведенных здесь текстовых шаблонов, соответствующих единичному символу ( любому, кроме % и), может следовать символ для создания текстового шаблона, соответствующего последовательным появлениям нуля или более раз шаблона единичного символа. Результирующий шаблон называется замыканием. Например, X соответствует нулевому или большему числу повторений символов X; XX - одному или более значений X; [ а - z ] - любой цепочке, содержащей нулевое или большее число строчных букв. [43]

Оно порождает число 32232, то есть элемент того же класса. Оно порождает число 2322232, которое в свою очередь порождает число 322232, то есть элемент того же класса. Оно порождает число 223222232, которое порождает число 23222232, а оно в свою очередь дает нам число 3222232, так что мы опять возвращаемся в указанный класс. В более общем виде: для любой цепочки двоек Т число 32Т32 порождает число Г322Т32, которое приводит к числу 322Т32, опять представляющему собой элемент данного класса. Итак, все числа, входящие в указанный класс, являются вечными. [44]

Страницы: 1 2 3 4