Входная цепочка

Cтраница 3

Таким образом, хотя мы обычно и не рассматриваем программу, как преобразование множества входных цепочек литер во множество выходных цепочек литер, такое рассмотрение тем не менее правомерно. [31]

При этом способе для исключения неоднозначности содержания ошибки целесообразным является указание на несоответствие участка входной цепочки синтаксической конструкции языка ( в примере ( выражению), ( отношению) или ( условию)), хотя можно было бы дать и другое толкование причин ошибок. [32]

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

Иначе говоря, неразрешим вопрос: как быстро растет длина используемой рабочей ленты при растущей длине входной цепочки в процессе распознавания нерегулярных бесконтекстных языков. [34]

Мы построим М 0 так, чтобы для каждой ДМТ М с данной сложностью нашлась хотя бы одна входная цепочка, которую допускает М, но отвергает М, или наоборот. Одна из способностей, которыми наделена машина Ма, состоит в возможности моделировать произвольную машину Тьюринга по ее описанию. Машина М0 будет распознавать, допускает ли машина Тьюринга М входную цепочку л; так, что при этом используется не более Si ( x) клеток, где Sx - некоторая функция. [35]

Стартовав из начального состояния ( в нашем примере это SJ, автомат переходит из состояния в состояние по мере чтения входной цепочки. Переход зависит от текущего входного символа, как указывают метки на дугах графа переходов. [36]

В утверждение автомате распознает ( или воспринимает) язык L может быть заложен един из двух смыслов: а) для любой входной цепочки w автомат А останавливается и указывает, что он принимает или отвергает w, в зависимости от того, выполняется или нет условие т t L; б) А останавливается, если w С L; в противном случае автомат не останавливается. [37]

Цепочка допускается из состояния S, если автомат может сделать спонтанный переход из S в S1, а затем допустить ( всю) входную цепочку из Si. [38]

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

РСП интерпретируется сетевой грамматикой, формально она может быть определена кортежем Fs ( У, L, N), где V - описание словарей, используемых при разборе входной цепочки; L - описание нестандартных функций, необходимых для эффективного разбора; N - описание РСП, представляющее собой описание множества так называемых кустов. Кустом называется вершина РСП с множеством дуг, выходящих из нее. Под разбором входной цепочки ( фразы языка) понимается проверка ее допустимости РСП. [40]

Произведенное при решении этой задачи сравнительное исследование различных схем четырехполюсников RC показывает значительное преимущество для диапазонного избирательного усилителя схемы несимметричного двойного Т - четырехполюсника с высоким соотношением импеданцев выходной и входных цепочек. Возможно применение как максимального [3], [5], так и нулевого варианта такого двойного Т - четырехполюсника. Их исследованию в настоящей работе уделено наибольшее внимание. [41]

При втором методе, называемом сверху - вниз выбираются по синтаксическому дереву языка последовательности все более м е л к и х понятий, начиная от верхней цели, и при анализе входной цепочки определяется, правильно ли выбрана эта последовательность. Если очередное понятие в последовательности не формируется, то происходит замена последовательности понятий от той же цели на новую, допустимую синтаксисом языка. В процессе анализа для тех узлов дерева, где имеется одна или несколько компонент, также возникает необходимость сформировать новую цель, являющуюся одной из этих компонент, и без достижения которой невозможно формирование следующего понятия в выбранной последовательности. [42]

Алгоритм Эрли, тщательно прослеживая все варианты параллельно, получает представление всех возможных вариантов анализа цепочки по отношению к КС-грамматике за время, которое может быть ограничено величиной / ( я3, где п - длина цепочки, а Д - константа, зависящая только от грамматики и не зависящая от входной цепочки. Более того, для некоторых подклассов КС-грамматик можно показать, что граница требуемого времени может быть снижена до п2 для линейных грамматик и некоторых других и до п для LR ( k) - грамматик со считыванием вперед k символов ( Кнут [17]) и некоторых других. [43]

Программа для п на Упрощенном Алголе. [44]

Языком, допускаемым программой Р, называется множество всех цепочек ( слов), допускаемых ею. Для входных цепочек, не принадлежащих языку, допускаемому программой Р, она может напечатать на выходной ленте символ, отличный от 1, и остановиться, а может даже и не остановиться вообще. [45]

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