Cтраница 2
В самом деле, пусть N - произвольное множество, возникшее в результате применения операции расщепления к одному из i-классов Kr ( i) данного множества автоматов М, не входящее ни в какое другое множество того же вида, а ат и ап - два произвольных состояния из N. Рассмотрим произвольное слово ptxp, имеющее длину i 1, и будем считать сначала, что рассматриваемое множество М состоит из автоматов Мили. [16]
Для произвольного слова а пусть a ( i) обозначает t - ю букву слова а, а х - длину слова а. [17]
Определим последовательность /: N - А следующим образом: / ( 0) Л; если же х 0, то рассмотрим запись числа х в р-ичной системе счисления, выпишем в порядке вхождения в нее все ненулевые цифры &i... А именно, произвольное слово Si0 Sin является значением функции / при значении аргумента iopn iipn - 1 - гп. [18]
Одноместная операция соединения слов ( описана в § 5 гл. Будучи применена к произвольному слову, эта операция в качестве результата дает то же слово. [19]
Используем это для доказательства такого факта: каждое слово из множества F эквивалентно некоторому слову вида rafh, где а и b - неотрицательные целые числа. Действительно, если задано произвольное слово из множества F, то можно применить равенство fr r2f для того, чтобы переставлять / и г, заменяя одновременно г на г2; таким путем мы можем сдвинуть все символы / вправо, а все символы г влево. [20]
Слово R - это одно из слов г3, f2, rfrf ( или их обратных), а сумма показателей степени элемента / в этих словах равна 0, 2, 2 ( или 0, - 2, - 2 для обратных) соответственно. Так как Т - произвольное слово из множества / % то сумма показателей степени элемента / в слове Т может быть льрбым числом. [21]
Включение ЕВ немедленно следует из определения множества В. Предположим теперь, что W - произвольное слово из В. [22]
Если г и s - два произвольных элемента группы, то существует элемент к Hs, такой, что гх s ( стр. Ясно, что если W - произвольное слово, представляющее элемент к r - 1s, то rW s; таким образом, если вершина, соответствующая элементу т, взята за начальную точку, то путь, описанный словом W, ведет от г-вершины к s - вершине. [23]
Типичная массовая алгоритмическая проблема для формальных языков состоит в том, что требуется установить существование алгоритма, который для произвольного языка L, заданного порождающей грамматикой или другой порождающей системой, устанавливает, обладает ли этот язык некоторым свойством. Например, проблема принадлежности связана с проверкой, принадлежит ли произвольное слово а языку L; в проблеме пустоты следует выяснить, пусто ли множество L; в проблеме конечности задача состоит в выяснении, является ли L конечным множеством. [24]
Действительно, в силу принятого выше определения вхождения пустое слово входит во всякое слово р, причем первое его вхождение не будет иметь слева от себя ни одной буквы. Отсюда же непосредственно следует, что применение указанной подстановки к произвольному слову р переведет его в слово хр. [25]
Она состоит в нахождении алгоритма, позволяющего по представлению А XR) K, где X и К конечны, и по произвольным словам и, v из / ( - свободной алгебры F с базой X определить, задают ли и и v один элемент в алгебре А. [26]
Мы тоже могли бы использовать один из двух доступных способов адресации для индексной адресации с 32-битным смещением, которое следует за командой. С другой стороны, большинству разработок типа RISC потребовалось бы по крайней мере 96 битов, а может и больше, для прибавления произвольного слова из памяти к другому произвольному слову из памяти, и тогда нужно было бы по крайней мере 4 цикла шины. [27]
Мы не будем здесь пытаться объяснять доказательство этого результата, скажем только, что оно использует нечто вроде диагонального метода, употребляемого для доказательства несчетности множества действительных чисел. Классической и наиболее важной проблемой разрешения для группового представления является проблема слов ( см. 1.1.9): существует ли алгоритм для определения по произвольному слову над множеством порождающих данного представления, является ли оно следствием определяющих соотношений, представления и, тем самым, определяет ли оно единичный элемент. Ответ на этот вопрос может быть и отрицательным, то есть существуют представления, проблема слов для которых алгоритмически неразрешима, более того, возможно выписать пример такого представления за сравнительно короткое время. [28]
Мы тоже могли бы использовать один из двух доступных способов адресации для индексной адресации с 32-битным смещением, которое следует за командой. С другой стороны, большинству разработок типа RISC потребовалось бы по крайней мере 96 битов, а может и больше, для прибавления произвольного слова из памяти к другому произвольному слову из памяти, и тогда нужно было бы по крайней мере 4 цикла шины. [29]
Она состоит из семи последовательных элементов строки. Тело третьего элемента строки содержит слово EQU L I LJ, а пятого - абсолютное или простое перемещаемое выражение, дополненное символами LJ до 55 - общего числа символов в теле пятого элемента строки либо одно из указанных выражений и произвольное слово языка ассемблера, резделенные пробелом. Это произвольное слово называется комментарием. Тело седьмого элемента строки содержит восемь пробелов. [30]