Cтраница 1
Свободные полугруппы - это первые математические объекты, с которыми сталкивается любой человек. Еще до школы ребенок обучается языку. Раннее обучение - в сильной степени опираясь на тот факт, что слова и предложения несут смысловое значение - обеспечивает цели общения, такие, как наименование предметов, выражение ощущений и, позднее - мыслей, их узнавание от других или другими членами социальной группы. Эта сторона языка, как носителя смысла, называется его семантическим аспектом. Это различение ведет к двум дополняющим друг друга математическим формализациям: математической теории связи, заложенной Шенноном ( Галлагер [1968], Берлекэмп [1968]) и основанной на теории вероятностей, и алгебраической лингвистике ( Хом-ский [1957], С. [1]
Ьа Ь2У свободной полугруппы а, Ь не является конечно определенной ( заметим, что оценка 4 здесь точная; все 3-порожденные подполугруппы свободных полугрупп конечно определены, причем для 2-порожденных из них попросту выполняется альтернатива - быть подполугруппой бесконечной моногенной полугруппы или быть изоморфной свободной полугруппе ранга 2, см. [30], с. Обратно, любая рекурсивно определенная полугруппа вложима в некоторую к. [2]
Пусть в произвольной свободной полугруппе F с конечным числом образующих задана любая система определяющих соотношений S, состоящая из конечного числа соотношений. Требуется найти единый конструктивный прием, позволяющий за конечное число шагов решить, являются любые два заданных слова полугруппы F с системой определяющих соотношений S тождественными или нетождественными. [3]
Доказать, что свободная полугруппа имеет лишь единственное неприводимое порождающее множество. [4]
Таким образом, свободные полугруппы позволяют сравнительно просто описывать работу автоматов. [5]
Ясно, что свободные полугруппы X и ( X 1) являются подмножествами группы Fr ( X), так как они задают заведомо редуцированные слова. Число символов алфавита X называют рангом свободной группы. [6]
Понятно, что любая свободная полугруппа удовлетворяет закону сокращения. [7]
Так как подполугруппа свободной полугруппы не обязательно свободна, то для полугрупповых автоматов утверждение, аналогичное предложению 4.3, неверно. [8]
Учитывая введенный ранее термин свободная полугруппа ( см. § 1), следует иметь в виду следующее. Свободная полугруппа никогда не является группой. [9]
Заранее заданная система образующих свободной полугруппы с единицей, между которыми в полугруппе нет никаких соотношений, кроме тех, которые следуют из аксиом, определяющих полугруппу. [10]
Отметим, что П есть свободная полугруппа с множеством 2 свободных образующих ( ср. G даже полугруппой операторов, так как справедливость требования ( 2) вытекает из ( 3) и ассоциативности умножения эндоморфизмов. Ясно также, что 2-допустимые подгруппы остаются и П - допустимымп, а 2-операторные гомоморфизмы будут и П - операторными. [11]
Отметим, что П есть свободная полугруппа с множеством S свободных образующих ( ср. G даже полугруппой операторов, так как справедливость требования ( 2) вытекает из ( 3) и ассоциативности умножения эндоморфизмов. Ясно также, что 2-допустимьте подгруппы остаются и П - допустимыми, а 2-операторные гомоморфизмы будут и П - операторнъши. [12]
Отсюда следует, что всякая свободная полугруппа обладает лишь единственным свободным порождающим множеством. [13]
Инициальный свободный автомат - это свободная полугруппа Рхъ единицей, на которой функция переходов определена как умножение слова на символ входного алфавита х справа. [14]
Напомним об одной характерном свойстве свободных полугрупп: для любой свободной полугруппы всегда можно найти однозначно определенный гомоморфизм полугрупп, переводящий ее в заданную полугруппу, причем так, что образующие элементы под действием гомоморфизма переходят в заранее указанные элементы заданной полугруппы. [15]